#include <iostream>
#include<stdlib.h>
using namespace std;
typedef struct BSTNode{int data; //每个结点的数据域
struct BSTNode *lchild, *rchild; //左右孩子指针
}
BSTnode, *BSTree;
bool Tree_Search(BSTree T,int key)//在根指针T所指二叉排序数中递归查找某关键字等于key的数据域
{BSTree p = T;
while(p){if(key == p->data)
return true; //查找结束
else p=(key<p->data)?(p->lchild):(p->rchild);//在左右子树中继续查找
}
return false;}
BSTree Tree_Insert(BSTree T, int key)//二叉排序树插入操作
{BSTree p = T;BSTree f,s;
while(p != NULL)
{f= p; if(key == p->data)
{ cout<<"要插入的节点已存在，不必再插入！"<<endl;
return T;}
p = (key > p->data)? p->rchild:p->lchild;}
s = new BSTnode;//生成新结点*s
s -> data = key;//新结点*s的数据域置为key
s -> lchild = s -> rchild = NULL;//把新结点*s作为叶子结点
if(T == NULL) return s;//把新结点*s链接到已找到的插入位置
if(key < f->data) f -> lchild = s;//将*s插入左子树
else f -> rchild = s;//将*s插入右子树
return T;}
void Tree_Delete(BSTree T, int key)//删除指定的节点
{BSTree p=T,q,f,s;while(p) //先寻找到要删除的节点
{if(key == p->data)//找到关键字等于key的结点*p，结束循环
{break;}
f = p;//*f为*p的双亲结点
p=(key<p->data)?p->lchild:p->rchild;//在*p的左右子树中继续查找
}
if(!p){cout<<"二叉树中没有节点,不能删除!"<<"\n"; }
else if(!p->lchild && !p->rchild)//被删结点为根结点
{if(p==T) T=NULL;
if(p == f->lchild)
f->lchild = NULL;//挂接到*f的左子树位置
else f->rchild = NULL;//挂接到*f的右子树位置
delete p;p = NULL;}
else if(!p->rchild && p->lchild)//被删结点*p无右子树，只需重接其左子树
{if (f->lchild == p) f->lchild = p->lchild;
else f->rchild = p->lchild;delete p;p = NULL; }
else if(!p->lchild && p->rchild)//被删结点*p无左子树，只需重接其右子树
{if(f->lchild == p) f->lchild = p->rchild;
else f->rchild = p->rchild;
delete p;p = NULL;}
else//被删结点*p左右子树均不空
{q = p;s = p->lchild;
while(s->rchild)//在*p的左子树中继续查找其前驱结点，即最右下结点
{q = s; s = s->rchild;//向右到尽头}
p->data = s->data;//s指向被删结点的“前驱”
if(q!=p) q->rchild=s->lchild;//重接*q的右子树
else q->lchild = s->lchild;//重接*q的左子树
delete s;s = NULL;}}
BSTree Create(); //创建二叉排序树{//依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
int key;BSTree T = NULL;//将二叉排序树T初始化为空树
cout<<"请输入节点数据值:(-1)为结束值"<<endl; cin>>key; while(key != -1)
{T=Tree_Insert(T, key);//将此结点插入二叉排序树T中
cin>>key;}
return T;}
void inorder(BSTree T) //中序遍历
{if(T){inorder(T->lchild);cout<<T->data<<" ";inorder(T->rchild);}
return;}
void menu()//菜单
{
cout<<"**********欢迎使用************"<<endl;
cout<<" -------1.建立二叉排序树-------"<<endl;
cout<<" -------2.插入节点-------------"<<endl;
cout<<" -------3.删除节点-------------"<<endl;
cout<<" -------4.查找节点-------------"<<endl;
cout<<" -------5.中序遍历-------------"<<endl;
cout<<" -------0.退出系统-------------"<<endl;
cout<<" ******************************"<<endl;
}
int main()
{
int choice1, choice2, key;
BSTree T = NULL;
menu();
do
{
cout<<"请输入你的选择"<<endl;
cin>>choice1;
switch(choice1)
{case 1:
T=create();
cout<<"二叉排序树创建成功!"<<endl;break;
case 2:
cout<<"请输入要插入的节点的关键字:"<<endl;cin>>key;
T=Tree_Insert(T, key);
cout<<endl;break;
case 3:
cout<<"请输入要删除的节点的关键字:"<<endl;cin>>key;
Tree_Delete(T, key);
cout<<endl;break;
case 5:
cout<<"------中序遍历的结果如下------"<<endl;inorder(T);
cout<<endl;break;
case 4:
cout<<"请输入要搜索节点的关键字:"<<endl;cin>>key;
if(Tree_Search(T, key)) {cout<<"节点已搜索到!"<<endl;}
else{cout<<"节点不存在!"<<endl;
cout<<"1.插入该节点"<<" "<<"2.不插入该节点"<<endl;
cout<<"请输入你的选择(1-2)"<<endl;cin>>choice2;switch(choice2)
{case 1: T = Tree_Insert(T, key);cout<<endl;
break; case 2:
break;}}}}while(choice1 != 0); cout<<endl; system("pause");
return 0;}
这段代码中存在多个错误，以下是这些错误和修改方法：
1、在 Create 函数的定义上面没有写返回值类型，应该加上 BSTree，即 BSTree Create()
2、在 Create 函数的定义中，有一行是 return T;，应该改成 return T;}，即加上右括号。
3、在 Tree_Delete 函数中，当要删除的节点为根节点且左右子树均为空时，删除后没有返回任何值，应该加上 return NULL;
4、在 Tree_Delete 函数中，删除非叶子节点时有可能会访问空指针，因此在访问 p->lchild 和 p->rchild 之前应该先检查 p 是否为空指针。
5、在 Tree_Delete 函数中，删除非叶子节点时，需要先找到要删除节点的前驱或后继节点，但是找前驱节点时的代码有误，应该改为：
q = p;
s = p->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
即先将 q 设为 p，然后在 p 的左子树中找到最右下的节点 s。
6、在 Create 函数中，读入数据的代码有误，应该把 cin>>key 放到 while 循环里面。
7、在 menu 函数中，输出菜单时，最后一行的省略号应该改成正确的菜单选项。
8、在 menu 函数中，第一行输出的欢迎语中，应该改成 欢迎使用二叉排序树系统。