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)
search(x->left, key);
else
search(x->right, key);
}
template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
search(root, key);
}
非递归方式进行查找
template<class T>
BSTNode<T>* BSTree<T>::interativeSearch(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>::interativeSearch(T key)
{
interativeSearch(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;
}
查找后继
template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
if(x->right!=NULL)
return minimum(x->right);
// 如果x没有右孩子。则x有以下两种可能：
// (1) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
// (2) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
BSTNode<T> *p = x->parent;
while(p!=NULL && x==p->right)
{
x = p;
p = p->parent;
}
return p;
}
插入
template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z)
{
BSTNode<T> *y = NULL;
BSTNode<T> *x = tree;
// 查找z的插入位置
while(x!=NULL)
{
y = x;
if(z->key < x->key)
x = x->left;
else // else if(z->key > x->key)
x = x->right;
// 若禁止插入相同键值
// else
// {
// free(z)；// 释放之前分配的结点
// return;
// }
}
z->parent = y;
if(y==NULL)
tree = z;
else if(z->key<y->key)
y->left = z;
else
y->right = z;
}