《二叉排序树的 建立 删除 插入.doc》由会员分享，可在线阅读，更多相关《二叉排序树的 建立 删除 插入.doc（4页珍藏版）》请在三一文库上搜索。
1、 二叉排序树-1403张柯 实验要求：1、编写算法实现二叉排序树的创建，插入与删除操作。 （ 创建时是根据给定数据的无序序列，按照输入顺序创建）希望下面的代码能够帮到你：#includeusing namespace std; typedef struct/二叉排序树存储表示int key;ElemType;typedef struct BSTElemType data;BST *lchild,*rchild;BST,*BSTree;typedef struct funvoid InsertBST(BSTree&T,ElemType e) /二叉树的插入BSTree S;if(!T)S=new
2、 BST;S-data=e;S-lchild=S-rchild=NULL;T=S;else if(e.keydata.key)InsertBST(T-lchild,e);else if(e.keyT-data.key)InsertBST(T-rchild,e);void CreatBST(BSTree&T)/二叉排序树的创立ElemType e;T=NULL;while(cine.key)InsertBST(T,e); cin.clear(); cin.sync(); void DeleteBST(BSTree &T,int key)/删除操作BSTree p,f,q,s;p=T;f=NULL
3、;while(p)if(p-data.key=key)break;f=p;if(p-data.keykey)p=p-lchild;else p=p-rchild;if(!p)return;if(p-lchild)&(p-rchild)q=p;s=p-rchild;while(s-rchild)q=s;s=s-lchild;p-data=s-data;if(q!=p)q-lchild=s-lchild;else q-rchild=s-rchild;delete s;return;else if(!p-rchild)q=p;p=p-lchild;else if(!p-lchild)q=p;p=p-
4、rchild;if(!f)T=p;else if(q=f-lchild) f-lchild=p;else f-rchild=p;delete q;BSTree SearchBST(BSTree T,int key)if(!T|key=T-data.key)return T;else if(keydata.key) return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key);void Display(BSTree T)/二叉排序树的中序递归遍历if(T)Display(T-lchild);coutdata.keyrchi
5、ld);fun;fun B;main()ElemType e;int n;BSTree T; coutendl; couttt*小伙伴们，咱们来玩个树表查找的游戏吧*endlendl;couttt *首先，让我们创建二叉排序树*endlendl;cout 那么小伙伴们，请按照可爱的齐老师给出的相应数据依次输入吧，每个数据以空格间隔，输入以EOF结束，输入的时候可要很细心哦 1 1endl; cout 请输入相应数据:; B.CreatBST(T);cout 好的小伙伴们，你们太棒了，这个游戏要是到现在结束，肯定太无趣了，所以呢，睁大眼睛看好了，为了更清楚的了解二叉排序树，我特意在这里给出了，你
6、所创建的二叉排序树的中序遍历结果：; B.Display(T);coutendlendl;cout1 OK,little guys,you are so excellent!,下面进行下一步，这一步也是实现动态动态查找的一部分,下面我们来实现二叉排序树的删除操作endlendl;coutn;B.DeleteBST(T,n);cout1 OK,我们已经将你最不喜欢的数字删除了，不信你看!endl;cout 此时中序遍历结果为： ;B.Display(T);coutendl;cout 是不是特别开心呀，小伙伴，是不是很神奇呀，嘿嘿endlendl;cout或许这些还不足以满足你，下面让我们再玩些花样，有的时候，对于一些资料，不光要删除，还要插入，下面我们来进行动态查找的第二步-插入1endl; coute.key;B.InsertBST(T,e);cout 哇，小伙伴，你已经暴走了，so crazy!,我已经帮你添加上了，不信你看endl;cout中序遍历结果为：;B.Display(T);coutendl;coutOk,这个游戏到此就要告一段落了，谢谢老师的观看，小伙伴们，我们下次再见哦endl;