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;
}
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);
}
#endif
测试代码:BSTreeTest.cpp
#include<iostream>
#include "BSTree.h"
using namespace std;
static int arr[] = {1,5,4,3,2,6};
int main()
{
int i,len;
BSTree<int> *tree = new BSTree<int>();
cout<<"依次添加:";
len = sizeof(arr)/sizeof(arr[0]);
for(i=0;i<len;++i)
{
cout<<arr[i]<<" ";
tree->insert(arr[i]);
}
cout<<"\n前序遍历:";
tree->preOrder();
cout<<"\n中序遍历:";
tree->inOrder();
cout<<"\n后序遍历:";
tree->postOrder();
cout<<endl;
cout<<"最小值:"<<tree->minimum()<<endl;
cout<<"最大值:"<<tree->maximum()<<endl;
cout<<"树的详细信息:"<<endl;
tree->print();
cout<<" \n删除根节点:"<<arr[3];
tree->remove(arr[3]);
cout<<"\n中序遍历:";
tree->inOrder();
cout<<endl;
// 销毁二叉树
tree->destroy();