Previous Table of Contents Next


7.5.3.2. The Tree Abstract Base Class

If a Node contains the data, a Tree controls how a user accesses the data:

   class Tree {
       friend class Node;
       friend ostream& operator<< (ostream&, const Tree&);
   public:
       Tree(int);
       Tree(const char*, const Tree&);
       Tree(const char*, const Tree&, const Tree&);
       Tree(const Tree& t) { p = t.p; ++p->use; }
       ~Tree() { if (--p->use == 0) delete p; }
       Tree& operator=(const Tree& t);
   private:
       Node* p;
   };

The only datum in a Tree object is a pointer to a Node. The three constructors after the public label allow a Tree to be built from an integer, or from a string literal (which is really a character pointer) and one or two other Trees.

Two function definitions and one declaration control memory allocation. The first of these is the copy constructor, which tells how to create a Tree from another Tree. It makes the newly created Tree point to the same Node as the Tree from which it is being created, and increments the use count to account for the fact that there is one more pointer to that Node than there was before. The Tree destructor just decrements the use count in the Node associated with the Tree being destroyed and frees the Node if the use count becomes zero. Although this particular program never assigns one Tree to another, the assignment operator is declared here for completeness. Its definition is deferred for later.

Using the << output operator on a Tree calls the print function of the corresponding Node. The print function is virtual, so the call is dynamically bound:

   ostream&
   operator<<(ostream& o, const Tree& t)
   {
       t.p->print(o); // virtual call
       return o;
   }

7.5.3.3. Deriving Classes from Node

So far, Nodes aren’t good for much because they contain no data. Indeed, because a Node is an abstract base class, we cannot actually create objects of that class. So we have no choice to to derive classes from Node.

The first class we will derive is one that represents integers:

   class IntNode: public Node {
       friend class Tree;
   private:
       int n;
       IntNode (int k): n (k) { }
       void print (ostream& o) const { o << n; }
   };

Strictly speaking, the private label is unnecessary because the members will be private anyway. The point is to ensure that ordinary users will not be able to create IntNode objects, because those objects are intended to be used only as part of the implementation of class Tree. For the same reason, we nominate class Tree as a friend.

Similarly, we define classes to represent unary and binary operators:

   class UnaryNode: public Node {
       friend class Tree;
   private:
       const char* op;
       Tree opnd;
       UnaryNode (const char* a, const Tree& b): op (a), opnd (b) { }
       void print (ostream& o) const
       {
           o << “(“ << op << opnd << “)”;
       }
   };
   
   class BinaryNode: public Node {
       friend class Tree;
   private:
       const char* op;
       Tree left;
       Tree right;
       BinaryNode (const char* a, const Tree& b, const Tree& c):
           op (a), left (b), right (c) { }
       void print (ostream& o) const {
           o << “(“ << left << op << right << “)”;
       }
   };

Each of these classes is a kind of Node that contains some extra information and has its own constructor and print function. Each class nominates Tree as a friend so that the Tree constructors can call the constructors for the corresponding types of nodes.

7.5.3.4. Constructing Tree Constructors

He‹re are the definitions of the Tree constructors:

   Tree::Tree(int n): p(new IntNode(n)) { }

   Tree::Tree(const char* op, const Tree& t):
       p(new UnaryNode(op, t)) { }

   Tree::Tree(const char* op, const Tree& left, const Tree& right):
       p(new BinaryNode (op, left, right)) { }

The first of these constructors tells how to build a Tree from an int, which allows an int argument to be passed to a Tree parameter. Thus

   Tree t = Tree(“*”, Tree(“-”, 5),    Tree(“+”, 3, 4));

means the same thing as

   Tree t = Tree(“*”,
       Tree(“-”, Tree(5)),
       Tree(“+”, Tree(3), Tree(4)));

but the former is easier to understand than the latter.

Each constructor uses new to allocate, in dynamic memory, an appropriate object of a class that is derived from Node, and stores the address of that object in the Tree it is constructing. The Node constructor automatically ensures that the use count starts out at 1.

7.5.3.5. How the Data Structures Work

Consider what happens when the main program above executes the subexpression cout << t. Variable t is a Tree, so this subexpression calls

   operator<<(ostream&, const Tree&)

which in turn extracts t.p. This is a pointer to a Node of some type—which type is not known until execution. When that pointer is used to call t->print, the type of node determines during execution which print function will be called.


Previous Table of Contents Next