二叉排序树操作：
实现二叉排序树的创建、遍历、查找、插入和删除操作。
说明：
1、按教材中算法创建二叉排序树；
2、实现二叉排序树的升序遍历；
3、给定元素值查找结点指针位置，找到返回其指针，并利用指针输出元素值，未找到则插入之；
4、删除指定元素值的结点，保持二叉排序树性质不变；
5、程序提供简单功能菜单
#include <iostream>
using namespace std;
//声明二叉排序树
typedef struct BSTNode
{int key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
//声明插入函数
void InsertKey(BSTree T,int it){ //插入节点函数，如果节点存在则返回不插入，如果不存在插入
BSTree Top=T;//Top指向当前访问的节点
BSTree Pt;//指向当前访问节点的父亲节点
while (Top!=NULL){ //如果当前节点不为空,
if (Top->key==it)//访问的节点不相同
return;
Pt=Top; //赋值父亲节点
if (it<Top->key){ //如果要插入的值比当前节点小
Top=Top->lchild; //Top指向当前节点的左孩子
}else //否则指向右孩子
Top=Top->rchild;
} //循环以后。Top指向了叶子节点
Top=new BSTNode;
Top->key=it;
Top->lchild=NULL;
Top->rchild=NULL;
if (T==NULL){ //如果根节点为空
T=Top;
}else {
if (it>Pt->key) //如果插入的节点比他的双亲值大
Pt->rchild=Top; //则插入到右枝上
else Pt->lchild=Top; //否则插入到左枝上
}
}
//定义先序遍历树
void pTreaval(BSTree T){
if (T){
cout <<T->key<<endl;
if (T->lchild!=NULL)
pTreaval(T->lchild);
if (T->rchild!=NULL)
pTreaval(T->rchild);
}
}
void MidTree(BSTree T){
BSTree top=T;
if(top!=NULL){ //如果节点不为空
MidTree(top->lchild); //先序遍历左子树
cout<<top->key<<endl;//输出节点数
MidTree(top->rchild);//先序遍历右子树
}
}
//定义创建二叉排序树函数
void InitBST(BSTree T){
int key;//声明要插入的数字
cout <<"请输入你要插入的数字："<<endl;
cin >>key;
if (key!=0)
T->key=key;
cout <<"请输入你要插入的数字："<<endl;
cin >>key;
while (key!=0){ //如果要插入的数不是0
InsertKey(T,key); //插入节点
cout <<"请输入你要插入的数字："<<endl;
cin >>key;
}
}
BSTree FaindBST(BSTree T,int k)
{//若二叉排序树t中没有关键字k，则插入，否则插入之。返回对应的节点的指针
BSTree p=T; //p的初值指向根结点
BSTree f; //f保存当前查找的结点
while(p!=NULL) //查找节点位置
{if (p->key==k) return p; //已有k，返回节点指针
f=p; //f保存当前查找的结点
p=(k<p->key)?p->lchild:p->rchild;//若k<p->key，在左子树上查找，否则在右子树上查找
}
p=new BSTNode;
p->key=k;
p->lchild=p->rchild=NULL;
if(T==NULL)
T=p;
else if (k<f->key)
f->lchild=p;
else
f->rchild=p;
return p;
}
//声明删除节点
int Delete(BSTree bst, int X){//在二叉排序树bst上，删除其关键字为X的结点。
BSTree f,p=bst,q,s;
while (p && p->key!=X) //查找值为X的结点
if (p->key>X)
{
f=p;
p=p->lchild;
}else{
f=p;
p=p->rchild;
}
if (p==NULL) {
cout<<"无你要删除的节点 "<<X<<endl;
return 0;
}
if (p->lchild==NULL) { //被删结点无左子树
if (f->lchild==p)
f->lchild=p->rchild;//将被删结点的右子树接到其双亲上
else
f->rchild=p->rchild;
}else { //被删结点有左子树
q=p;
s=p->lchild; //s指向被删结点左子树的根
while (s->rchild !=NULL) {//查左子树中最右下的结点（中序最后结点）
q=s;
s=s->rchild;
}
p->key=s->key; //结点值用其左子树最右下的结点的值代替
if (q==p) // 查左子树中没有右孩子
p->lchild=s->lchild;//被删结点左子树的根结点无右子女
else
q->rchild=s->lchild; //s是被删结点左子树中序最后一个结点
delete s;
}
return 0;
}//算法结束
//输出功能菜单函数：
void MenuReport(){
cout <<"功能菜单介绍如下："<<endl;
cout <<endl<<"1. 创建二叉排序树；"<<endl;
cout <<"2. 升序遍历二叉排序树；"<<endl;
cout <<"3. 查找元素，找不到则插入；"<<endl;
cout <<"4. 删除二叉排序树；"<<endl;
}
//声明功能函数
int Method(){
char chase;
MenuReport();
cout <<endl<<"请选择操作："<<endl;
cin >>chase;
while(chase!='0'){
switch(chase){
case '0':
return 0;
break;
case '1':
cout<<"输入方法介绍：如果输入数字为非0的数且树中无此节点则插入之，存在不插入。若为0插入结束！！"<<endl;
BSTree T;//声明根节点
T=new BSTNode;
T->lchild=NULL;
T->rchild=NULL;
//实例化树
InitBST(T);
break;
case '2':
//升序遍历
cout <<endl<<"升序遍历二叉树结果："<<endl;
MidTree( T);
break;
case '3':
//查找节点，如果存在则返回节点的指针，如果不存在，则插入之
int key1;
BSTree FT;
cout <<"请输入："<<endl;
cin>>key1;
FT=FaindBST(T,key1);
if (FT!=NULL){
cout <<FT->key<<" 所在节点指针已返回！"<<endl;
}
break;
case '4':
cout<<"调用删除函数："<<endl;
int del;
cout <<"请输入你要删除的节点："<<endl;
cin>>del;
Delete(T,del);
break;
default :
cout <<"输入错误！！！无此操作，请重新输入!!!"<<endl;
break;
}
MenuReport();
cout <<" 请选择操作："<<endl;
cin >>chase;
}
return 0;
}
int main (){
//调用函数
Method();
return 0;
}