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

介绍
二叉查找树，又称二叉搜索树、有序二叉树、排序二叉树。
它是特殊的二叉树，对于二叉树，假设x为二叉树中的任意一个结点，x结点包含关键字key，结点x的key值记为key[ x ]。如果y是x的左子树中的一个结点，则key[ y ] <= key[ x ]；如果y是x的右子树中的一个结点，则key[ y ] >= key[ x ]；那么，这棵树就是二叉查找树，如下图所示：

二叉查找树具有以下性质：

1）若任意结点的左子树非空，则左子树上所有结点的值均小于它的根节点的值
2）若任意结点的右子树非空，则右子树上所有结点的值均大于它的根节点的值
3）任意结点的左、右子树叶分别为二叉查找树
4）没有键值相等的结点

算法实现
结点和二叉查找树的定义

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);
};

遍历

前序遍历

template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  cout<<tree->key<<" ";
  preOrder(tree->left);
  preOrder(tree->right);
 }
}

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

中序遍历

template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  inOrder(tree->left);
  cout<<tree->key<<" ";
  inOrder(tree->right);
 }
}

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

后序遍历