关于二叉树的基本操作请转到我的另一篇博客： http://blog.csdn.net/qq_30091945/article/details/77531651
概念
Binary Search Tree，也可称为二叉搜索树，二叉排序树。 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
查找操作
算法如下： 1）树为空，返回NULL 2）树非空时，对根节点的键值与x即你想那个比较，如果相等则返回根节点 3）如果x小于根结点的键值，在左子树进行查找x 4）如果x大于根结点的键值，在右子树进行查找x 代码如下：
代码语言：javascript复制//按值查找结点
BinarySearchTree* Find(BinarySearchTree* BST,int data){
BinarySearchTree* cur = BST;
//搜索树为空，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//根节点值与data相等，返回根节点
if(cur->data == data){
return cur;
}else if(cur->data < data){
//比data小，则在左子树里寻找
cur = cur->lchild;
}else{//否则在右子树里寻找
cur = cur->rchild;
}
}
}查找最大最小值
根据二叉搜索树的定义可以知道，最大值一定在最右分支的端节点上，最小值在最左分支的端节点上。 查找最小值算法如下：
代码语言：javascript复制//查找最小值
BinarySearchTree* FindMin(BinarySearchTree* BST){
BinarySearchTree* cur = BST;
//搜索树为空时，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//左子树为空时，返回该节点
if(cur->lchild == NULL){
return cur;
}else{//否则在左子树里找最小值
cur = cur->lchild;
}
}
}查找最大值算法如下：
代码语言：javascript复制//查找最大值
BinarySearchTree* FindMax(BinarySearchTree* BST){
BinarySearchTree* cur = BST;
//搜索树为空时，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//右子树为空时，返回该节点
if(cur->rchild == NULL){
return cur;
}else{//否则在右子树里找最小值
cur = cur->rchild;
}
}
}插入操作
算法如下： 1）树空时，直接构造一个根节点即可。 2）树非空时，x小于根节点键值时，那么递归插入到左子树上。 3）x大于根节点键值时，那么队规插入到右子树上。 算法如下：
代码语言：javascript复制//插入函数
BinarySearchTree* Insert(BinarySearchTree* BST,int data){
//搜索树为空，则构建根节点
if(!BST){
BST = new BinarySearchTree;
BST->data = data;
BST->lchild = BST->rchild = NULL;
}else{
//若data小于根节点的值，则插入到左子树
if(data < BST->data){
BST->lchild = BST->Insert(BST->lchild,data);
}else if(data > BST->data){
//若data小于根节点的值，则插入到左子树
BST->rchild = BST->Insert(BST->rchild,data);
}
}
return BST;
}删除操作
算法如下: 1）树空时，直接返回NULL 2）树非空时，如果要删除的是叶子节点时，直接删除，并把父节点的相应指针置为NULL。 3）要删除的只有一个孩子时，把其父节点的指针指向要删除的结点的孩子结点。 4）要删除的有两个孩子结点时，用另一个结点代替被删除的结点：右子树的最小结点或者左子树的最大结点 下面是3种情况图示：
算法如下：
代码语言：javascript复制//删除操作
BinarySearchTree* Delete(BinarySearchTree* BST,int data){
if(!BST){//树空时，直接返回NULL
return BST;
}else if(data < BST->data){
//data小于根节点时，到左子树去删除data
BST->lchild = this->Delete(BST->lchild,data);
}else if(data > BST->data){
//data大于根节点时，到右子树去删除data
BST->rchild = this->Delete(BST->rchild,data);
}else{//data等于根节点时
if(BST->lchild && BST->rchild){
//左右子树都不空时，用右子树的最小来代替根节点
BinarySearchTree* tmp = this->FindMin(BST->rchild);
BST->data = tmp->data;
//删除右子树的最小结点
this->Delete(BST->rchild,tmp->data);
}else{//当左右子树都为空或者有一个空时
BinarySearchTree* tmp = BST;
if(!BST->lchild){//左子树为空时
BST = BST->rchild;
}else if(!BST->rchild){//右子树为空时
BST = BST->lchild;
}
delete tmp;
}
}
return BST;
}删除最小值
算法如下： 1）如果树为空，则返回NULL 2）当树不为空时，直至搜索左子树直至当前结点左子树为空，同时保存当前结点的父节点。 3）若当前结点为树的根结点时，直接返回根结点的右子树 4）否则，若当前结点的右子树为空，即当前结点为叶子结点时，父节点的左子树置NULL，释放当前结点。若当前结点的右子树不为空时，把当前结点的右子树放到父节点的左子树上，释放当前结点。返回跟结点。
代码语言：javascript复制//删除最小值
BinarySearchTree* DeleteMin(BinarySearchTree* BST){
BinarySearchTree* cur = BST; //当前结点
BinarySearchTree* parent = BST; //当前结点的父节点
if(cur == NULL){
return BST;
}
//当前结点的左子树非空则一直循环
while(cur->lchild != NULL){
parent = cur; //保存当前结点父节点
cur = cur->lchild; //把当前结点指向左子树
}
if(cur == BST){//当前结点为根结点，即只有右子树
BST = BST->rchild;
}else{
if(cur->rchild == NULL){//右子树为空，即为叶子节点
parent->lchild = NULL; //父节点左子树置空
delete cur;
}else{//右子树非空
parent->lchild = cur->rchild; //把当前结点右子树放到父节点的左子树上
delete cur;
}
}
return BST;
}删除最大值
算法如下： 1）如果树为空，则返回NULL 2）当树不为空时，直至搜索右子树直至当前结点右子树为空，同时保存当前结点的父节点。 3）若当前结点为树的根结点时，直接返回根结点的左子树 4）否则，若当前结点的左子树为空，即当前结点为叶子结点时，父节点的右子树置NULL，释放当前结点。若当前结点的左子树不为空时，把当前结点的左子树放到父节点的右子树上，释放当前结点。返回跟结点。
代码语言：javascript复制//删除最大值
BinarySearchTree* DeleteMax(BinarySearchTree* BST){
BinarySearchTree* cur = BST; //当前结点
BinarySearchTree* parent = BST; //当前结点的父节点
if(cur == NULL){
return BST;
}
//当前结点右子树非空则一直循环
while(cur->rchild != NULL){
parent = cur; //保存当前结点父节点
cur = cur->rchild; //把当前结点指向右子树
}
if(cur == BST){//当前结点为根结点，即只有左子树
BST = BST->lchild;
}else{
if(cur->lchild == NULL){//左子树为空，即为叶子节点
parent->rchild = NULL; //父节点右子树置空
delete cur;
}else{//左子树非空
parent->rchild = cur->lchild; //把当前结点左子树放到父节点的右子树上
delete cur;
}
}
return BST;
}下面是基于下图所示二叉搜索树的具体实例程序结果：
全部代码如下：
代码语言：javascript复制#include <iostream>
#include <stack>
using namespace std;
int MAX = -32767;
class BinarySearchTree{
private:
int data;
BinarySearchTree* lchild;
BinarySearchTree* rchild;
public:
//查找最小值
BinarySearchTree* FindMin(BinarySearchTree* BST){
BinarySearchTree* cur = BST;
//搜索树为空时，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//左子树为空时，返回该节点
if(cur->lchild == NULL){
return cur;
}else{//否则在左子树里找最小值
cur = cur->lchild;
}
}
}
//查找最大值
BinarySearchTree* FindMax(BinarySearchTree* BST){
BinarySearchTree* cur = BST;
//搜索树为空时，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//右子树为空时,返回该节点
if(cur->rchild == NULL){
return cur;
}else{//否则在左子树里找最小值
cur = cur->rchild;
}
}
}
//按值查找结点
BinarySearchTree* Find(BinarySearchTree* BST,int data){
BinarySearchTree* cur = BST;
//搜索树为空，返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//根节点值与data相等，返回根节点
if(cur->data == data){
return cur;
}else if(cur->data < data){
//比data小，则在左子树里寻找
cur = cur->lchild;
}else{//否则在右子树里寻找
cur = cur->rchild;
}
}
}
//插入函数
BinarySearchTree* Insert(BinarySearchTree* BST,int data){
//搜索树为空，则构建根节点
if(!BST){
BST = new BinarySearchTree;
BST->data = data;
BST->lchild = BST->rchild = NULL;
}else{
//若data小于根节点的值，则插入到左子树
if(data < BST->data){
BST->lchild = BST->Insert(BST->lchild,data);
}else if(data > BST->data){
//若data小于根节点的值，则插入到左子树
BST->rchild = BST->Insert(BST->rchild,data);
}
}
return BST;
}
//二叉搜索树的构造,利用data数组构造二叉搜索树
BinarySearchTree* Create(int* data,int size){
BinarySearchTree* bst = NULL;
for(int i = 0 ; i < size ; i ){
bst = this->Insert(bst,data[i]);
}
return bst;
}
//递归前序遍历
void PreorderTraversal(BinarySearchTree* T){
if(T == NULL){
return;
}
cout<<T->data<<" "; //访问根节点并输出
T->PreorderTraversal(T->lchild); //递归前序遍历左子树
T->PreorderTraversal(T->rchild); //递归前序遍历右子树
}
//递归中序遍历
void InorderTraversal(BinarySearchTree* T){
if(T == NULL){
return;
}
T->InorderTraversal(T->lchild); //递归中序遍历左子树
cout<<T->data<<" "; //访问根节点并输出
T->InorderTraversal(T->rchild); //递归中序遍历左子树
}
//递归后序遍历
void PostorderTraversal(BinarySearchTree* T){
if(T == NULL){
return;
}
T->PostorderTraversal(T->lchild); //递归后序遍历左子树
T->PostorderTraversal(T->rchild); //递归后序遍历右子树
cout<<T->data<<" "; //访问并打印根节点
}
//删除操作
BinarySearchTree* Delete(BinarySearchTree* BST,int data){
if(!BST){//树空时，直接返回NULL
return BST;
}else if(data < BST->data){
//data小于根节点时，到左子树去删除data
BST->lchild = this->Delete(BST->lchild,data);
}else if(data > BST->data){
//data大于根节点时，到右子树去删除data
BST->rchild = this->Delete(BST->rchild,data);
}else{//data等于根节点时
if(BST->lchild && BST->rchild){
//左右子树都不空时，用右子树的最小来代替根节点
BinarySearchTree* tmp = this->FindMin(BST->rchild);
BST->data = tmp->data;
//删除右子树的最小结点
BST->rchild = this->Delete(BST->rchild,tmp->data);
}else{//当左右子树都为空或者有一个空时
BinarySearchTree* tmp = BST;
if(!BST->lchild){//左子树为空时
BST = BST->rchild;
}else if(!BST->rchild){//右子树为空时
BST = BST->lchild;
}
delete tmp;
}
}
return BST;
}
int getdata(BinarySearchTree* BST){
return BST->data;
}
//删除最小值
BinarySearchTree* DeleteMin(BinarySearchTree* BST){
BinarySearchTree* cur = BST; //当前结点
BinarySearchTree* parent = BST; //当前结点的父节点
if(cur == NULL){
return BST;
}
//当前结点的左子树非空则一直循环
while(cur->lchild != NULL){
parent = cur; //保存当前结点父节点
cur = cur->lchild; //把当前结点指向左子树
}
if(cur == BST){//当前结点为根结点，即只有右子树
BST = BST->rchild;
}else{
if(cur->rchild == NULL){//右子树为空，即为叶子节点
parent->lchild = NULL; //父节点左子树置空
delete cur;
}else{//右子树非空
parent->lchild = cur->rchild; //把当前结点右子树放到父节点的左子树上
delete cur;
}
}
return BST;
}
//删除最大值
BinarySearchTree* DeleteMax(BinarySearchTree* BST){
BinarySearchTree* cur = BST; //当前结点
BinarySearchTree* parent = BST; //当前结点的父节点
if(cur == NULL){
return BST;
}
//当前结点右子树非空则一直循环
while(cur->rchild != NULL){
parent = cur; //保存当前结点父节点
cur = cur->rchild; //把当前结点指向右子树
}
if(cur == BST){//当前结点为根结点，即只有左子树
BST = BST->lchild;
}else{
if(cur->lchild == NULL){//左子树为空，即为叶子节点
parent->rchild = NULL; //父节点右子树置空
delete cur;
}else{//左子树非空
parent->rchild = cur->lchild; //把当前结点左子树放到父节点的右子树上
delete cur;
}
}
return BST;
}
};
int main()
{
int size;
cout<<"请输入结点个数："<<endl;
cin>>size;
int* data;
data = new int[size];
cout<<"请输入每个结点的值："<<endl;
for(int i = 0 ; i < size ; i ){
cin>>data[i];
}
BinarySearchTree* bst;
bst = new BinarySearchTree;
bst = bst->Create(data,size);
cout<<"前序遍历（递归）："<<endl;
bst->PreorderTraversal(bst);
cout<<endl;
cout<<"中序遍历（递归）："<<endl;
bst->InorderTraversal(bst);
cout<<endl;
cout<<"后序遍历（递归）："<<endl;
bst->PostorderTraversal(bst);
cout<<endl;
BinarySearchTree* bst_max;
bst_max = bst->FindMax(bst);
cout<<"二叉搜索树的最大值为："<<endl;
cout<<bst_max->getdata(bst_max);
cout<<endl;
cout<<"删除最大值后："<<endl;
bst = bst->DeleteMax(bst);
cout<<"前序遍历（递归）："<<endl;
bst->PreorderTraversal(bst);
cout<<endl;
cout<<"中序遍历（递归）："<<endl;
bst->InorderTraversal(bst);
cout<<endl;
cout<<"后序遍历（递归）："<<endl;
bst->PostorderTraversal(bst);
cout<<endl;
cout<<"二叉搜索树的最小值为："<<endl;
BinarySearchTree* bst_min;
bst_min = bst->FindMin(bst);
cout<<bst_min->getdata(bst_min);
cout<<endl;
cout<<"删除最小值后："<<endl;
bst = bst->DeleteMin(bst);
cout<<"前序遍历（递归）："<<endl;
bst->PreorderTraversal(bst);
cout<<endl;
cout<<"中序遍历（递归）："<<endl;
bst->InorderTraversal(bst);
cout<<endl;
cout<<"后序遍历（递归）："<<endl;
bst->PostorderTraversal(bst);
cout<<endl;
int num;
cout<<"请输入要删除的结点："<<endl;
cin>>num;
bst = bst->Delete(bst,num);
cout<<"删除之后："<<endl;
cout<<"前序遍历（递归）："<<endl;
bst->PreorderTraversal(bst);
cout<<endl;
cout<<"中序遍历（递归）："<<endl;
bst->InorderTraversal(bst);
cout<<endl;
cout<<"后序遍历（递归）："<<endl;
bst->PostorderTraversal(bst);
cout<<endl;
return 0;
} 截图如下：
