1  #pragma once
   2  #include <memory>
   3  
   4  class InternalNode;
   5  
   6  class Node {
   7      public:
   8          const InternalNode* getParent() const {return parent_;}
   9          InternalNode* getParent() {return parent_;}
  10          virtual ~Node(){}
  11  
  12      protected:
  13          explicit Node(InternalNode* const parent) : parent_(parent) {}
  14  
  15      private:
  16          InternalNode* parent_;
  17  };
  18  
  19  
  20  class InternalNode : public Node {
  21      public:
  22          explicit InternalNode(InternalNode* parent) : Node(parent){}
  23  
  24          const Node* getLeftBranch() const {return leftBranch_.get();}
  25          const Node* getRightBranch() const {return rightBranch_.get();}
  26  
  27          void setVacant(Node* const node) 
  28              {(leftBranch_?rightBranch_:leftBranch_) = node_ptr(node);}
  29  
  30          const Node* getBranch(const bool branch) const 
  31              {return (branch?rightBranch_:leftBranch_).get();}
  32  
  33          bool isFull() const {return rightBranch_!=0;}
  34  
  35      private:
  36          typedef std::tr1::shared_ptr<Node> node_ptr;
  37          node_ptr leftBranch_;
  38          node_ptr rightBranch_;
  39  };
  40  
  41  
  42  class LeafNode : public Node {
  43      public:
  44          LeafNode(InternalNode* const parent, char symbol) : Node(parent), symbol_(symbol) {}
  45          char getSymbol() const {return symbol_;}
  46  
  47      private:
  48          char symbol_;
  49  };