bst.cpp

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

#include <iostream.h>
#include <stdlib.h>
#include <assert.h>

typedef int BELEM;
#include "..\include\book.h"

#include "..\include\bintree.h"

// Binary Search Tree Class
#include "..\include\bst.h"

// Clear all nodes from the BST
void BST::clearhelp(BinNode* rt) {
  if (rt == NULL) return;
  clearhelp(rt->leftchild());
  clearhelp(rt->rightchild());
  delete rt;
}

void BST::inserthelp(BinNode*& rt, const BELEM val) {
  if (rt == NULL)                  // Empty tree: create node
    rt = new BinNode(val, NULL, NULL);
  else if (val < rt->value())      // Check left
    inserthelp(rt->left, val);
  else inserthelp(rt->right, val); // Check right
}

void BST::removehelp(BinNode*& rt, const BELEM val) {
  if (rt == NULL) cout << val << " is not in the tree.\n";
  else if (val < rt->value())      // Check left
    removehelp(rt->left, val);
  else if (val > rt->value())      // Check right
    removehelp(rt->right, val);
  else {                           // Found it: remove it
    BinNode* temp = rt;
    if (rt->left == NULL)          // Only a right child
      rt = rt->right;              //   so point to right
    else if (rt->right == NULL)    // Only a left child
      rt = rt->left;               //   so point to left
    else {                         // Both children are non-empty
      temp = deletemin(rt->right); // Replace with min value
      rt->setValue(temp->value()); //   in right subtree
    }
    delete temp;                   // Return node to free store
  }
}

BinNode* BST::deletemin(BinNode*& rt) {
  assert(rt != NULL);       // There must be a node to delete
  if (rt->left != NULL)     // Continue left
    return deletemin(rt->left);
  else                      // Found it
    { BinNode* temp = rt; rt = rt->right; return temp; }
}

BinNode* BST::findhelp(BinNode* rt, const BELEM val) const {
  if (rt == NULL) return NULL; // Empty tree: nothing to find
  else if (val < rt->value())                  // Check left
    return findhelp(rt->leftchild(), val);
  else if (val == rt->value()) return rt;      // Found it
  else return findhelp(rt->rightchild(), val); // Check right
}

// Print the nodes of a BST; use indentation to indicate tree shape
void BST::printhelp(const BinNode *rt, const int level) const {
  if (rt == NULL) return;               // Empty tree
  printhelp(rt->leftchild(), level+1);  // Print left subtree
  for (int i=0; i<level; i++)           // Indent to level
    cout << "  ";
  cout << rt->value() << "\n";          // Print node value
  printhelp(rt->rightchild(), level+1); // Print right subtree
}

#define visit(X) cout << rt->element << " ";
void preorder(BinNode* rt)  // rt is the root of a subtree
{
  if (rt == NULL) return;   // Empty subtree
  visit(rt);  // visit performs whatever action is desired
  preorder(rt->leftchild());
  preorder(rt->rightchild());
}