// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Test for variable nodes implemented with simple inheritance // The test vehicle is an expression tree. // The program builds and traverses a simple tree. #include "book.h" typedef char Operator; typedef string Operand; // Node implementation with simple inheritance class VarBinNode { // Node abstract base class public: virtual ~VarBinNode() {} virtual bool isLeaf() = 0; // Subclasses must implement }; class LeafNode : public VarBinNode { // Leaf node private: Operand var; // Operand value public: LeafNode(const Operand& val) { var = val; } // Constructor bool isLeaf() { return true; } // Version for LeafNode Operand value() { return var; } // Return node value }; class IntlNode : public VarBinNode { // Internal node private: VarBinNode* left; // Left child VarBinNode* right; // Right child Operator opx; // Operator value public: IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) { opx = op; left = l; right = r; } // Constructor bool isLeaf() { return false; } // Version for IntlNode VarBinNode* leftchild() { return left; } // Left child VarBinNode* rightchild() { return right; } // Right child Operator value() { return opx; } // Value }; void traverse(VarBinNode *root) { // Preorder traversal if (root == NULL) return; // Nothing to visit if (root->isLeaf()) // Do leaf node cout << "Leaf: " << ((LeafNode *)root)->value() << endl; else { // Do internal node cout << "Internal: " << ((IntlNode *)root)->value() << endl; traverse(((IntlNode *)root)->leftchild()); traverse(((IntlNode *)root)->rightchild()); } } int main() { VarBinNode* temp1; VarBinNode* temp2; VarBinNode* root; string string1 = "Hello1"; string string2 = "Another string"; temp1 = new LeafNode(string1); temp2 = new LeafNode(string2); root = new IntlNode('+', temp1, temp2); traverse(root); return 0; }