genmain.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include "book.h"

typedef int ELEM;

class GTNode {
private:
  ELEM element;
  GTNode* rent;
  GTNode* leftchild;
  GTNode* rightsib;
public:
  GTNode(const ELEM);              // Constructor
  GTNode(const ELEM, GTNode*, GTNode*, GTNode*); // Constructor
  ~GTNode();                       // Destructor
  ELEM value();                    // Return node's value
  bool isLeaf();                   // TRUE if node is a leaf
  GTNode* parent();                // Return node's parent
  GTNode* leftmost_child();        // Return node's first child
  GTNode* right_sibling();         // Return node's right sibling
  void setValue(ELEM);             // Set node's value
  void insert_first(GTNode* n);    // Insert as the first child
  void insert_next(GTNode* n);     // Insert as the right sibling
  void remove_first();             // Remove first child from tree
  void remove_next();              // Remove right sibling from tree
};


class GenTree {
private:
  GTNode* rt;
public:
  GenTree();                       // Constructor
  ~GenTree();                      // Destructor
  void clear();                    // Send all nodes to free store
  GTNode* root();                  // Return the root of the tree
  void newroot(ELEM, GTNode*, GTNode*);
};


GTNode::GTNode(const ELEM value) {
  rent = leftchild = rightsib = NULL;
  element = value;
}

GTNode::GTNode(const ELEM value, GTNode* par, GTNode* leftc, GTNode* rights) {
  element = value;
  rent = par; leftchild = leftc; rightsib = rights;
}  

/* GTNode::GTNode(const ELEM value, GTNode* parent, GTNode* first,
                            GTNode* sib) {
  element = value;
  rent = parent;
  leftchild = first;
  rightsib = sib;
} */

GTNode::~GTNode() { }

ELEM GTNode::value() { return element; }

bool GTNode::isLeaf() { return leftchild == NULL; }

GTNode* GTNode::parent() { return rent; }

GTNode* GTNode::leftmost_child() { return leftchild; }

GTNode* GTNode::right_sibling() { return rightsib; }

void GTNode::setValue(ELEM value) { element = value; }

void GTNode::insert_first(GTNode* n) {
  n->rightsib = leftchild;
  n->rent = this;
  leftchild = n;
}

void GTNode::insert_next(GTNode* n) {
  n->rightsib = rightsib;
  n->rent = rent;
  rightsib = n;
}

void GTNode::remove_first() {
  if (leftchild == NULL) return;
  GTNode* temp = leftchild;
  leftchild = leftchild->rightsib;
  delete temp;  // BAD -- lose all its subtree!
}

void GTNode::remove_next() {
  if (rightsib == NULL) return;
  GTNode* temp = rightsib;
  rightsib = rightsib->rightsib;
  delete temp;  // BAD -- lose all its subtree!
}

/////////////////////////////////////////////

GenTree::GenTree() { rt = NULL; }

GenTree::~GenTree() { rt = NULL; } // AWFUL! Throw away the storage

void GenTree::clear() { rt = NULL; } // AWFUL! Throw away the storage

GTNode* GenTree::root() { return rt; }

void GenTree::newroot(ELEM value, GTNode* first, GTNode* sib) {
  clear();
  rt = new GTNode(value, (GTNode*)NULL, first, sib);
}


void print(GTNode* rt) { // Preorder traversal from the root
  if (rt->isLeaf()) cout << "Leaf: ";
  else cout << "Internal: ";
  cout << rt->value() << "\n";  // Print or take other action
  GTNode* temp = rt->leftmost_child();
  while (temp != NULL)
    { print(temp);  temp = temp->right_sibling(); }
}

main()
{
  GenTree tree;
  GTNode* ptr;
  GenTree tree2;
  GTNode* ptr2;

  tree.newroot(1, NULL, NULL);
  ptr = tree.root();
  cout << "Print the tree with one node\n";
  print(tree.root());
  ptr->insert_first(new GTNode(2));
  cout << "Print the tree with two nodes\n";
  print(tree.root());
  ptr = ptr->leftmost_child();
  cout << "ptr now at node " << ptr->value() << "\n";
  ptr->insert_next(new GTNode(3));
  cout << "Print the tree with three nodes\n";
  print(tree.root());
  ptr->insert_next(new GTNode(4));
  cout << "Print the tree with four nodes\n";
  print(tree.root());
  ptr = ptr->right_sibling();
  cout << "ptr now at node " << ptr->value() << "\n";
  ptr->insert_first(new GTNode(5));
  cout << "Print the tree with 5 nodes\n";
  print(tree.root());

  tree2.newroot(11, NULL, NULL);
  ptr2 = tree2.root();
  ptr2->insert_first(new GTNode(12));
  ptr2 = ptr2->leftmost_child();
  ptr2->insert_next(new GTNode(13));

  return(0);
}