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

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

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

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

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const
{
 if(x==NULL || x->key==key)
  return x;
 if(key<x->key)
  return search(x->left, key);
 else
  return search(x->right, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
 search(root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const
{
 while(x!=NULL && x->key!=key)
 {
  if(key<x->key)
   x = x->left;
  else
   x = x->right;
 }
 return x;
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(T key)
{
 iterativeSearch(root, key);
}

template<class T>
BSTNode<T>*  BSTree<T>::maximum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->right!=NULL)
  tree = tree->right;
 return tree;
}

template<class T>
T BSTree<T>::maximum()
{
 BSTNode<T> *p = maximum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

template<class T>
BSTNode<T>*  BSTree<T>::minimum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->left!=NULL)
  tree = tree->left;
 return tree;
}

template<class T>
T BSTree<T>::minimum()
{
 BSTNode<T> *p = minimum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
 if(x->left!=NULL)
  return maximum(x->left);
 // 如果x没有左孩子。则x有以下两种可能：
    // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode<T> *p = x->parent;
    while(p!=NULL && x==p->left)
    {
     x = p;
     p = p->parent;
 }
 return p;
}