varnodei.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 66 行

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include "..\include\book.h"
typedef char Operator;
typedef char* Operand;

class VarBinNode {                   // Node base class
public:
  // isLeaf is a "pure" virtual function, which means VarBinNode
  // contains no definition.  Each derived class must define isLeaf.
  virtual bool isLeaf() = 0;
};

class LeafNode : public VarBinNode { // Leaf node subclass
private:
  Operand var;                       // Operand value
public:
  LeafNode(const Operand& val) { var = val; } // Constructor
  bool isLeaf() { return TRUE; }     // Version for this subclass
  Operand& value() { return var; }   // Return node value
};

class IntlNode : public VarBinNode { // Internal node subclass
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 this subclass
  VarBinNode* leftchild() { return left; }   // Left child
  VarBinNode* rightchild() { return right; } // Right child
  Operator& value() { return opx; }          // Value
};

void traverse(VarBinNode *rt) {      // Preorder traversal
  if (rt == NULL) return;            // Nothing to visit
  if (rt->isLeaf())                  // Do leaf node
    cout << "Leaf: " << ((LeafNode *)rt)->value() << "\n";
  else {                             // Do internal node
    cout << "Internal: " << ((IntlNode *)rt)->value() << "\n";
    traverse(((IntlNode *)rt)->leftchild());
    traverse(((IntlNode *)rt)->rightchild());
  }
}

int main()
{
  VarBinNode* temp1;
  VarBinNode* temp2;
  VarBinNode* root;
  char *string1 = "Hello1";
  char *string2 = "Another string";

  temp1 = new LeafNode(string1);
  temp2 = new LeafNode(string2);
  root = new IntlNode('+', temp1, temp2);
  traverse(root);
  return(0);
}