二叉查找树解析及其C++实现(3)

template<class T>
void BSTree<T>::insert(T key)
{
 BSTNode<T> *z = NULL;
 
 // 如果新建结点失败，则返回
 if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL)
  return;
 
 insert(root,z);
}

删除

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)
{
 BSTNode<T> *x = NULL;
 BSTNode<T> *y = NULL;
 
 if(z->left==NULL || z->right==NULL)
  y = z;
 else
  y = successor(z);
 
 if(y->left!=NULL)
  x = y->left;
 else
  x = y->right;
 
 if(x!=NULL)
  x->parent = y->parent;
 
 if(y->parent==NULL)
  tree = x;
 else if(y==y->parent->left)
  y->parent->left = x;
 else
  y->parent->right = x;
 
 if(y!=z)
  z->key = y->key;
 return y;
}

template<class T>
void BSTree<T>::remove(T key)
{
 BSTNode<T> *z, *node;
 
 if((z=search(root,key))!=NULL)
  if((node=remove(root,z))!=NULL)
   delete node;
}

打印

template<class T>
void BSTree<T>::print(BSTNode<T> *tree, T key, int direction)
{
 if(tree!=NULL)
 {
  if(direction==0)
   cout<<setw(2)<<tree->key<<"is root"<<endl;
  else
   cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl;
  print(tree->left,tree->key,-1);
  print(tree->right,tree->key,1);
 }
}

template<class T>
void BSTree<T>::print()
{
 if(root!=NULL)
  print(root,root->key,0);
}

销毁

template<class T>
void BSTree<T>::destroy(BSTNode<T> *&tree)
{
 if(tree==NULL)
  return ;
 if(tree->left!=NULL)
  return destroy(tree->left);
 if(tree->right!=NULL)
  return destroy(tree->right);
 
 delete tree;
 tree=NULL;
}

template<class T>
void BSTree<T>::destroy()
{
 destroy(root);
}

二叉查找树完整实现：BSTree.h

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

#include<iomanip>
#include<iostream>
using namespace std;

template<class T>
class BSTNode
{
 public:
  T key; // 关键字（键值）
  BSTNode *left; // 左孩子
  BSTNode *right; // 右孩子
  BSTNode *parent; // 父结点
 
  BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
   key(value),parent(p),left(l),right(r) {}
};

template<class T>
class BSTree
{
 private:
  BSTNode<T> *root; // 根结点
 
 public:
  BSTree() {};
  ~BSTree() {};
 
  // 前序遍历
  void preOrder();
  // 中序遍历
  void inOrder();
  // 后序遍历
  void postOrder();
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(T key);
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(T key);
 
  // 查找最小结点（返回键值）
  T minimum();
  // 查找最大结点（返回键值）
  T maximum();
 
  // 找结点（x）的后继结点。即查找二叉树中键值大于该结点的最小结点
  BSTNode<T>* successor(BSTNode<T> *x);
  // 找结点（x）的前驱结点。即查找二叉树中键值小于该结点的最大结点
  BSTNode<T>* predecessor(BSTNode<T> *x);
 
  // 将键值为key的结点插入到二叉树中
  void insert(T key);
 
  // 删除键值为key的结点
  void remove(T key);
 
  // 销毁二叉树
  void destroy();
 
  // 打印二叉树
  void print();
 
 private:
  // 重载函数，提供内部接口
  // 前序遍历
  void preOrder(BSTNode<T> *tree) const;
  // 中序遍历
  void inOrder(BSTNode<T> *tree) const;
  // 后序遍历
  void postOrder(BSTNode<T> *tree) const;
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(BSTNode<T> *x, T key) const;
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const;
 
  // 查找最小结点（返回键值）
  BSTNode<T>* minimum(BSTNode<T> *tree);
  // 查找最大结点（返回键值）
  BSTNode<T>* maximum(BSTNode<T> *tree);
 
  // 将结点z插入到二叉树tree中
  void insert(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 删除二叉树中的结点z，并返回该结点
  BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 销毁二叉树
  void destroy(BSTNode<T>* &tree);
 
  // 打印二叉树
  void print(BSTNode<T>* &tree, T key, int direction);
};