二叉排序树的创建、删除、插入等操作

安徽工程大学计算机与信息学院课程设计报告课程名称《数据结构》课题名称二叉排序树的创建、删除、插入操作专业计算机科学与技术班级计算机121班学号3120701140姓名殷世军联系方式13095530869指导教师姚红燕计算机与信息学院2实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：二叉排序树插入算法伪代码如下：二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1.实验分析：程序的主要流程图：typedefstructBiTNode{//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;1.若root是空树，则将结点s作为根结点插入；否则2.若s-data＜root-data，则把结点s插入到root的左子树中；否则3.把结点s插入到root的右子树中。1.若结点p是叶子，则直接删除结点p；2.若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则3.1查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4删除结点s；计算机与信息学院3主要模块：1）主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于key2的数据元素；}2）创建二叉排序树模块BiTreeCreatBST(intn){建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；返回根结点T；输出过程；}3）删除模块DeleteNode(BiTree&T,intx)否是开始建树：①依次输入n个关键字②插入二叉排序树中③中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束计算机与信息学院4{从二叉树排序树T中删除任意结点,其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；}4）插入模块voidInsertBST1(BiTree&T,BiTNode*s){在二叉树排序树T中，插入一个结点s(递归算法)；被CreatBST函数调用；}5）查找模块BiTreesearchBST1(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；若成功，返回指向该数据元素结点的指针；否则返回空指针；}2.源程序代码：#includeiostream.usingnamespacestd;计算机与信息学院5typedefintKeyType;typedefstructtree//声明树的结构{structtree*left;//存放左子树的指针structtree*right;//存放又子树的指针KeyTypekey;//存放节点的内容}BSTNode,*BSTree;//声明二叉树的链表BSTreeinsertBST(BSTreetptr,KeyTypekey)//在二叉排序树中插入结点{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTreef,p=tptr;//p的初值指向根结点while(p)//查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲{if(p-key==key)//树中已有key，无须插入returntptr;f=p;//f保存当前查找的结点，即f是p的双亲p=(keyp-key)?p-left:p-right;}p=(BSTree)malloc(sizeof(BSTNode));//生成新结点p-key=key;p-left=p-right=NULL;if(tptr==NULL)//原树为空，新插入的结点为新的根tptr=p;elseif(keyf-key)f-left=p;elsef-right=p;returntptr;}BSTreecreateBST()//建立二叉树{BSTreet=NULL;//根结点KeyTypekey;cinkey;while(key!=-1){t=insertBST(t,key);cinkey;}returnt;}voidinorder_btree(BSTreeroot)//中序遍历打印二叉排序树{计算机与信息学院6BSTreep=root;if(p!=NULL){inorder_btree(p-left);coutp-key;inorder_btree(p-right);}}intsearchBST(BSTreet,KeyTypekey)//查找{if(key==t-key)return1;if(t==NULL)return0;if(keyt-key)returnsearchBST(t-left,key);elsereturnsearchBST(t-right,key);}BSTreedeleteBST(BSTreetptr,KeyTypekey)//删除{BSTreep,tmp,parent=NULL;p=tptr;while(p){if(p-key==key)break;parent=p;p=(keyp-key)?p-left:p-right;}if(!p)returnNULL;tmp=p;if(!p-right&&!p-left)/*p的左右子树都为空*/{if(!parent)//要删根，须修改根指针tptr=NULL;elseif(p==parent-right)parent-right=NULL;elseparent-left=NULL;free(p);}elseif(!p-right)//p的右子树为空，则重接p的左子树{p=p-left;if(!parent)//要删根，须修改根指针计算机与信息学院7tptr=p;elseif(tmp==parent-left)parent-left=p;elseparent-right=p;free(tmp);}elseif(!p-left)//的左子树为空，则重接p的左子树{p=p-right;if(!parent)//要删根，须修改根指针tptr=p;elseif(tmp==parent-left)parent-left=p;elseparent-right=p;free(tmp);}elseif(p-right&&p-left)//p有左子树和右子树，用p的后继覆盖p然后删去后继{//另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树parent=p;//由于用覆盖法删根，则不必特殊考虑删根p=p-right;while(p-left){parent=p;p=p-left;}tmp-key=p-key;if(p==parent-left)parent-left=NULL;elseparent-right=NULL;free(p);}returntptr;}intmain(){KeyTypekey;intflag,test;charcmd;BSTreeroot;do{cout\n\nendl;计算机与信息学院8cout\t\t*******请选择你要执行的操作:********endl;cout\nendl;cout\t\tC.创建一棵二叉排序树\n;cout\t\tE.结束本程序\n;cout\n\n\t\t************************************endl;flag=0;do{if(flag!=0)cout选择操作错误！请重新选择！\n;fflush(stdin);cincmd;flag++;}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');if(cmd=='c'||cmd=='C'){cout请输入你所要创建的二叉树的结点的值，以-1结束：\n;root=createBST();do{flag=0;cout\n\n中序遍历二叉树：endl;inorder_btree(root);cout\nendl;cout\t\t************请选择你要对这棵二叉树所做的操作:**************endl;cout\t\t****endl;cout\t\t**S......查找你想要寻找的结点**endl;cout\t\t**I......插入你想要插入的结点**endl;cout\t\t**D......删除你想要删除的结点**endl;cout\t\t**Q......结束对这棵二叉树的操作**endl;cout\t\t****endl;cout\t\t***********************************************************endl;do{if(flag!=0)cout选择操作错误！请重新选择！\n;fflush(stdin);scanf(%c,&cmd);flag++;}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');switch(cmd)计算机与信息学院9{case's':case'S':cout请输入你要查找结点的关键字：\n;cinkey;test=searchBST(root,key);if(test==0)cout\n对不起，你所查找的结点key不存在!;elsecout\n成功找到结点\nkey;break;case'i':case'I':cout请输入你要插入结点的关键字：\n;cinkey;root=insertBST(root,key);//注意必须将值传回根break;case'd':case'D':cout请输入你要删除结点的关键字：\n;cinkey;root=deleteBST(root,key);//注意必须将值传回根if(root==NULL)cout\n对不起，你所删除的结点key不存在!\n;elsecout\n成功删除结点key;break;}}while(cmd!='q'&&cmd!='Q');}}while(cmd!='e'&&cmd!='E');return0;}实验内容计算机与信息学院103.测试用例：1,程序运行时菜单显示如下：当输入的二叉树序列为：{2,6,9,8,4}时，创建二叉排序树，并输出结果如下：1.查找9结点时，运行结果如下：计算机与信息学院112.删除结点6时运行结果如下：3.插入结点7时运行结果如下：计算机与信息学院12实验内容计算机与信息学院134.实验总结：通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。在过程中和同学相互讨论，询问老师，不断进步。也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。