二叉排序树的建立和删除.doc

《二叉排序树的建立和删除.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、二叉排序树的建立和删除一、要求：输入一组关键值，建立相应的二叉排序树，完成节点的查找和删除操作。要求：（1）可以实现删除根结点、叶子结点及其他任意节点的功能；（2）可随时显示操作的结果。二、算法：1、二叉排序树的生成：向一个二叉排序树b中插入一个结点s的算法，（1）若b是空树，则将s所指结点作为根结点插入；否则（2）若s->data等于b的根结点的数据域之值，则返回；否则（3）若s->data小于b的根结点的数据域之值，则把s所指根结点插入到左子树中；否则（4）把s所指结点插入到右子树中。2、二叉排序树的查找：在二叉排序树

2、b中查找x的过程为：（1）若b是空树，则搜索失败，否则（2）若x等于b的根结点的数据域之值，则查找成功；否则（3）若x小于b的根结点的数据域之值，则搜索左子树；否则（4）查找右子树3、二叉排序树的插入：算法同“生成”。4、二叉排序树的删除删除二叉排序树b中一个数据域为x的结点的过程为：（1）首先查找到数据域为x的结点p；（2）若p所指没有左子树，则用右子树的根代替被删的结点；（3）若p所指结点有左子树，则在其左子树中找到最右结点r来代替被删的结点（即将r所指结点的右指针置成p所指结点的右子树的根，然后用p所指结点的左子树的

3、根结点代替被删的p所指结点）。5、二叉排序树的显示：采用中序遍历输出，显示结果是将值从小到大排列。三、平台：WindowsXPVC6.0一、程序清单：#include#includetypedefintKeytype;;typedefstructnode{Keytypekey;structnode*lchild,*rchild;}BSTNode;typedefBSTNode*BSTree;BSTreeCreateBST();voidSearchBST(BSTreeT,Keytyp

4、eKey);voidInsertBST(BSTree*T,KeytypeKey);voidDelBST(BSTree*T,KeytypeKey);voidInorderBST(BSTreeT);voidmain(){BSTreeT;charch1,ch2;KeytypeKey;cout<<"建立一棵二叉排序树"<

5、

6、ch1=='Y'){cout<<"请选择以下操作"<

7、ndl;cout<<"2----------二叉排序树上的查找"<>ch2;switch(ch2){case'1':CreateBST();break;case'2':cout<<"请输入要查找的数据:";cin>>Key;SearchBST

8、(T,Key);cout<<"查找完毕"<>Key;InsertBST(&T,Key);cout<<"插入操作完毕"<>Key;DelBST(&T,Key);cout<<"删除操作完毕"<

9、k;default:ch1='n';}}}BSTreeCreateBST(){BSTreeT;KeytypeKey;T=NULL;cout<<"请输入一组关键字,以零结束"<>Key;while(Key){InsertBST(&T,Key);cout<<"请输入下一个关键字"<>Key;}returnT;}voidSearchBST(BSTreeT,KeytypeKey){BSTNode*p=T;while(p){if(p->key==Key){cout<<"已找到"<

10、eturn;}p=(Keykey)?p->lchild:p->rchild;}cout<<"没有找到。。。";}voidInsertBST(BSTree*T,KeytypeKey){BSTNode*f,*p;p=(*T);while(p){if(p->key==Key){cout<<"树中已有K