二叉排序树的实现一、实验内容与要求1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。

二、实验方案1.选择链表的方式来构造节点，存储二叉排序树的节点。

//树的结构struct BSTNode{//定义左右孩子指针struct BSTNode *lchild,*rchild;//节点的关键字TElemType key;};int depth=0;//定义一个 struct BSTNode 类型的指针typedef BSTNode *Tree;2.对树的操作有如下方法：// 创建二叉排序树Tree CreatTree(Tree T)；//二叉树的深度，返回一个int值为该树的深度int TreeDepth(Tree T)//树状输出二叉树，竖向输出void PrintTree(Tree T , int layer)；//查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点Status SearchBST(Tree T , TElemType key , Tree f,Tree &p)；//向树中插入节点Status InsertBST(Tree &T , TElemType e)；//删除节点Status Delete(Tree &T)；//删除指定节点，调用Delete(Tree &T)方法Status DeleteData(Tree &T , TElemType key)；//非递归先序遍历void x_print(Tree T);//非递归中序遍历Void z_print(Tree T );//非递归后序遍历void h_print(Tree T);3.对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现//自定义类型以 SElemType作为栈中指针返回的值的类型//也就是要返回一个节点的指针typedef Tree SElemType;//栈的结构struct Stack{//栈底指针SElemType *base;//栈顶指针SElemType *top;//栈的容量int stacksize;};4.栈的操作方法：//创建一个空栈Status InitStack(Stack &S)；//获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem)//获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem)//删除栈顶元素Status DeleteTop(Stack &S)//往栈中压入数据Status Push(Stack &S,SElemType elem)//判断栈是否为空Status IsEmpty(Stack S)三、代码实现#include <iostream>#include <math.h>using namespace std;//定义宏#define OK 1#define ERROR 0#define STACK_INIT_SIZE 10#define STACK_INCREMENT 2//定义宏分别为栈的初始容量和栈的增加容量#define STACK_INIT_SIZE 10#define STACK_INCREMENT 2typedef int TElemType;//树的结构struct BSTNode{//定义左右孩子指针struct BSTNode *lchild,*rchild;//节点的关键字TElemType key;};int depth=0;//定义一个 struct BSTNode 类型的指针typedef BSTNode *Tree;//自定义类型以 SElemType作为栈中指针返回的值的类型//也就是要返回一个节点的指针typedef Tree SElemType;//栈的结构struct Stack{//栈底指针SElemType *base;//栈顶指针SElemType *top;//栈的容量int stacksize;};//自定义类型typedef int Status;//创建一个空栈Status InitStack(Stack &S){//给栈指针分配空间S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//如果分配空间失败则退出if(!S.base)exit(OVERFLOW);//栈底、栈顶指针相等表示栈为空//S.base=S.top;//此句代码若以如上句格式则在执行时会出现内存非法访问的错误S.top=S.base;//初始化栈的容量S.stacksize=STACK_INIT_SIZE;return OK;}//获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem){if(S.top==S.base){cout<<"gai zhan yi jing wei kong "<<endl;return ERROR;}else{elem=*--S.top;}return elem;}//获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem){//如果为空栈则返回ERRORif(S.base==S.top){cout<<"gai zhan yi jing wei kong"<<endl;return ERROR;}//如果栈不为空则返回栈顶元素else{elem=*(S.top-1);}return elem;}//删除栈顶元素Status DeleteTop(Stack &S){//判断栈是否为空if(S.base==S.top){cout<<"gai zhan yi jing wei kong "<<endl;return ERROR;}//如果栈不为空则删除栈顶元素else{--S.top;}return OK;}//往栈中压入数据Status Push(Stack &S,SElemType elem){//如果栈的容量超过初始化容量则增加栈的容量if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;}//添加数据*S.top++=elem;return OK;}//判断栈是否为空Status IsEmpty(Stack S){if(S.base==S.top)return OK;elsereturn ERROR;}/////////////////////////////////////////////////////////////////// ///////////以下的代码主要是对树的操作///////////////////////////// /////////////////////////////////////////////////////////////////////创建空树Status InitTree(Tree &T){T=NULL;return OK;}//查找关键字//如果关键字存在则返回所在节点的父节点//如果关键字不存在则返回叶子所在的节点Status SearchBST(Tree T,TElemType key,Tree f,Tree &p) {if(!T){p=f;return ERROR;}else if(T->key==key){p=T;return OK;}else if(T->key>key)return SearchBST(T->lchild,key,T,p);else if(T->key<key)return SearchBST(T->rchild,key,T,p);}//向树中插入节点Status InsertBST(Tree &T,TElemType e){Tree p;if(!SearchBST(T,e,NULL,p)){Tree s=(Tree)malloc(sizeof(BSTNode));s->key=e;s->lchild=s->rchild=NULL;if(!p){T=s;}else if(p->key>e){p->lchild=s;}else if(p->key<e){p->rchild=s;}}elsereturn ERROR;}// 创建二叉排序树Tree CreatTree(Tree T){TElemType elem;cout<<"请输入数据，以0结束输入操作"<<endl;cin>>elem;while(elem!=0 && elem>0){int k= InsertBST(T,elem);if(k){cout<<"请输入数据，以0结束输入操作"<<endl;cin>>elem;}else{cout<<"插入错误或存在重复元素"<<endl;//异常退出return ERROR;}}return T;}//删除节点Status Delete(Tree &T){Tree p,q;if(T->lchild!=NULL && T->rchild!=NULL){p=T;q=T->lchild;T=q;while(q->rchild!=NULL){q=q->rchild;}q->rchild=p->rchild;free(p);return OK;}if(T->rchild==NULL && T->lchild!=NULL){p=T;T=T->lchild;free(p);return OK;}else if(T->lchild==NULL && T->rchild!=NULL) {p=T;T=T->rchild;free(p);return OK;}else if(T->rchild==NULL && T->lchild==NULL){T=NULL;free(T);return OK;}}//删除指定节点Status DeleteData(Tree &T,TElemType key){if(!T){cout<<"找不到要删除的元素，请重新选择!"<<endl;return ERROR;}if(T->key==key){Delete(T);}else if(T->key>key)DeleteData(T->lchild,key);else if(T->key<key)DeleteData(T->rchild,key);return OK;}//先序遍历void x_print(Tree T){//Tree f;Stack S;InitStack(S);if(T==NULL){cout<<"树为空"<<endl;}while(T!=NULL || !IsEmpty(S)){if(T!=NULL){cout<<T->key<<" ";Push(S,T);T=T->lchild;}else{Pop(S,T);T=T->rchild;}}}//z中序遍历void z_print(Tree T ){// Tree f;Stack S;InitStack(S);if(T==NULL){cout<<"树为空"<<endl;}while(T!=NULL || !IsEmpty(S)){if(T!=NULL){Push(S,T);T=T->lchild;}else{Pop(S,T);cout<<T->key<<" ";T=T->rchild;}}}//后序遍历void h_print(Tree T){Stack S;InitStack(S);Tree f=NULL;if(T==NULL){cout<<"树为空"<<endl;}while(T!=NULL || !IsEmpty(S)){while(T!=NULL){Push(S,T);T=T->lchild;}getTop(S,T);if(T->rchild==NULL || T->rchild==f){cout<<T->key<<" ";Pop(S,f);T=NULL;}else{T=T->rchild;}}}//二叉树的深度int TreeDepth(Tree T){int left,right,max;if(T!=NULL){left=TreeDepth(T->lchild);right=TreeDepth(T->rchild);max=left>right?left:right;return max+1;}else{return ERROR;}}//竖向输出//树状输出二叉树void PrintTree(Tree T,int layer){int k;if(T==NULL)return ;PrintTree(T->rchild,layer+1);for(k=0;k<layer;k++)cout<<" ";cout<<T->key<<"\n";PrintTree(T->lchild,layer+1);}void main(){int key;int h;Tree tree;InitTree(tree);tree=CreatTree(tree);h=TreeDepth(tree);cout<<"树状输出为："<<endl;PrintTree(tree,h);if(!tree){exit(-1);}cout<<"\n\n---------------请输入你要选择的操作--------------------\n"<<endl;cout<<"a.删除二叉树中的元素 b.向二叉树中添加元素"<<endl;cout<<"c.先根遍历二叉树 d.中根遍历二叉树 "<<endl;cout<<"e.后根遍历二叉树 o.退出操作 "<<endl;cout<<"\n\n------------------------------------------------------\n"<<endl;//int key;char select;cin>>select;while(select!='o'){switch(select){case 'o':exit(0);break;case 'a':if(!tree){cout<<"树以为空，请重新选择操作!"<<endl;cin>>select;}else{cout<<"请输入要删除的元素"<<endl;cin>>key;DeleteData(tree,key);cout<<"树状输出为："<<endl;PrintTree(tree,h);}break;case 'b':cout<<"请输入要插入的元素"<<endl;cin>>key;InsertBST(tree,key);cout<<"树状输出为："<<endl;PrintTree(tree,h);break;case 'c':cout<<"先根遍历结果为："<<endl;x_print(tree);cout<<endl;break;case 'd':cout<<"中根遍历结果为："<<endl;z_print(tree);cout<<endl;break;case 'e':cout<<"后根遍历结果为："<<endl;h_print(tree);cout<<endl;break;default:cout<<"输入错误"<<endl;exit(-1);break;}cout<<"---------------请输入你要选择的操作--------------------"<<endl;cout<<"a.删除二叉树中的元素 b.向二叉树中添加元素"<<endl;cout<<"c.先根遍历二叉树 d.中根遍历二叉树 "<<endl;cout<<"e.后根遍历二叉树 o.退出操作 "<<endl;cout<<"--------------------------------------------------------"<<endl;cin>>select;}}四、实验结果和数据处理输入数据同选择操作结果如上图所示操作现象：输入操作的时候如果输入的不是数值（比如字母）就会出现插入操作错误的提示，然后异常退出操作；或者当输入的关键字已在树中存在，也会提示“重复输入”然后异常退出（这点存在不足，应该修改为提示之后重新输入操作）删除现象：如果要删除的关键字不存在则会提示不存在该关键字然后重新输入，如果树为空则会提示树为空并重新选择操作遍历现象：如果树为空，则不会退出操作，而是提示“树为空”。