实验三-全线索链表应用

实验三全线索链表应用问题定义及需求分析1.1课题目的和任务问题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针next。通过该结点构造全线索二叉链表。实验要求：设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例1.2数据形式输入数据形式：通过键盘输入数据输入值的范围：输入值的范围均为float型，范围为1.2e-38至3.4e+38。输出数据形式：输出到显示器。1.3程序功能将全线索作用于二叉排序树中，通过对其进行中序遍历线索化，实现通过线索搜索某个节点的前驱和后继，并且利用线索，实现对整个树中数据的中序线索输出，并且能够在删除树中某个节点后，实现对该树的重新线索化。1.4测试数据7//树中元素的个数5271368//依次输入的树中元素值3//需要输出前驱和后继的元素值7//删除的元素值8//重新线索化后，需要输出前驱和后继的元素值1.概要设计2.1抽象数据类型需要定义一个全线索二叉树，该树中含有数据，左右孩子，以及分别指向前驱和后继的指针。通过前驱和后继指针，将建立的二叉树中序线索化，从而实现对数据更方便和快速的获取。2.2主程序流程及各模块之间的调用关系开始输入结点数，并以此输入数据创建树，并存入一个结点数据InitTree()插入数据InsertTree()是否还有未存数据？中序线索化InOrderThreading()中序线索输出该树InOrderThrPrint()输入某个数值输入需删除数值删除该元素DeleteTree()去线索化RemoveThr()中序线索化InOrderThrPrint()中序线索输出InOrderThrPrint()结束否是中序线索搜索并输出该数的前驱和后继SearchPN()未找到，删除失败删除成功输入某个数值中序线索搜索并输出该数的前驱和后继SearchPN()2.详细设计3.1存储结构实现typedefstructType{//数据类型结构体声明floatnum;}Type;typedefstructBiTNode{//二叉树结构体声明structTypedata;structBiTNode*lchild,*rchild,*prior,*next;}BiTNode,*BiTree;3.2负责模块的伪码算法（1）intvisit(Typee,BiTreeT){//找到相同元素并返回它的前驱和后继if(T-data==e)return1;elsereturn0;}（2）constintInOrderTraverse_Thr(BiTreeT,Typee,int(*visit)(Typee,BiTreeT),Type&prior,Type&next){//中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继B=T-next;while(B非空且不等于T){if(visit(e,B)){//找到等于e的B结点值if(B前驱等于T){next=B-next-data;//B只有后继return2;}elseif(B后继等于T){prior=B-prior-data;//B只有前驱return3;}else{//B前驱和后继都不等于T(prior,next)=(B-prior-data,B-next-data);return1;//前驱和后继都存在}}B=B-next;}return0;}（3）constintSearchPN(BiTreeThrt,BiTreeT){//利用全线索查找所需元素的前驱和后继cine;//输入要查找的元素m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);//全线索中序查找某个元素的前驱和后继if(m==1){输出前驱和后继}elseif(m==2){前驱不存在，输出后继}elseif(m==3){后继不存在，输出前驱}else{查找失败，树中无该元素}return1;}3.调试分析4.1问题分析与解决方法对于给定输入数，查找它的前驱和后继，需要考虑该数是否存在前驱和后继，如果没有前驱和后继，则需要输出不存在标志。利用线索指针很容易进行判断，如果需要查找的元素的前驱是线索的头（线索的头是个空结点），那么该元素就不存在前驱，只存在后继；而如果需要查找的元素的后继是线索的头，那么它就不存在后继，只有前驱。因此通过if进行判断，就可以成功输出需要查询的元素的前驱和后继。4.2算法的时空分析在树中查找某个元素并输出该元素的前驱和后继的整个时间复杂度最多为On，空间复杂度为1O。4.3算法的改进设想全线索的应用主要是为了方便树的遍历，能够快速的访问某个节点的前驱和后继，因此可以考虑将线索应用于平衡二叉树上，从而进一步提高平衡二叉树获取数据的速度。4.4经验和体会在整个程序的编写过程中，出现一个问题，如果是首次线索化，便可以通过线索成功输出该树，但当删除某个节点后，再次进行线索化，然后利用线索输出该树就无法得到完整的树。后来经过调试发现，由于第一次的线索化，该树内的各个线索指针已被赋值，所以第二次线索化实际上是失败的，因此需要先对树进行去线索化操作（把线索指针指空）后，再对其进行线索化，这样才能输出正确的数据。可见，程序各个模块之间的影响不容小觑，必须对程序各个模块的功能和影响有个整体的把握才不至于出现不合设想的错误。4.使用说明按照操作提示，通过键盘输入数据即可。输入的节点数据可以为小数，但是数量数据必须为正整数。5.测试结果（截屏）（1）前驱和后继都存在的数：（2）只存在前驱的数：（3）只存在后继的数：6.附录7.1个人负责模块的程序代码intvisit(Typee,BiTreeT){//找到相同元素并返回它的前驱和后继if(T-data.num==e.num)return1;elsereturn0;}constintInOrderTraverse_Thr(BiTreeT,Typee,int(*visit)(Typee,BiTreeT),Type&prior,Type&next){//中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继BiTreeB=T-next;while(B!=NULL&&B!=T){if(visit(e,B)){if(B-prior==T){//该点的前驱为T，说明它无前驱next.num=B-next-data.num;return2;}elseif(B-next==T){//该点的后继为T，说明它无后继prior.num=B-prior-data.num;return3;}else{//该点既有前驱也有后继prior.num=B-prior-data.num;next.num=B-next-data.num;return1;}}B=B-next;}return0;}constintSearchPN(BiTreeThrt,BiTreeT){//利用全线索查找所需元素的前驱和后继Typee,prior,next;intm;coutPleaseinputanumbertobesearchedandprintitspriorandnext:endl;//输入需要查找的元素,将输出它的中序遍历的前驱和后继cine.num;m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);//全线索中序查找某个元素的前驱和后继if(m==1){//前驱和后继均有的情形coutThepriorofnumbere.numisprior.num,;coutanditsnextisnext.num.endl;}elseif(m==2){//只有后继的情形coutThepriorofnumbere.numisnotexisted,;coutanditsnextisnext.num.endl;}elseif(m==3){//只有前驱的情形coutThepriorofnumbere.numisprior.num,;coutanditsnextisnotexisted.endl;}else{//未找到该数的情形coutThenumbersearchedisnotexistedendl;}return1;}7.2程序全部代码#includestdlib.h#includeiostreamusingnamespacestd;typedefstructType{//数据类型结构体声明floatnum;}Type;typedefstructBiTNode{//二叉排序树结构体声明structTypedata;structBiTNode*lchild,*rchild,*prior,*next;}BiTNode,*BiTree;intInitTree(BiTree&T,Typee){//创建二叉排序树T=(BiTree)malloc(sizeof(BiTNode));if(!T)return0;T-data.num=e.num;T-lchild=T-rchild=NULL;T-prior=T-next=NULL;return1;}intDestroyTree(BiTree&T){//递归销毁二叉排序树if(T==NULL){return0;}DestroyTree(T-lchild);DestroyTree(T-rchild);free(T);return1;}intSearchTree(BiTreeT,Typekey,BiTree&p){//非递归算法，搜索二叉排序树中元素while(T){if(key.num==T-data.num){p=T;return1;}elseif(key.numT-data.num){p=T;T=T-lchild;}else{p=T;T=T-rchild;}}return0;}intInsertTree(BiTree&T,Typee){//二叉排序树中元素插入BiTreep;if(!SearchTree(T,e,p)){BiTrees;s=(BiTree)malloc(sizeof(BiTNode));s-data.num=e.num;s-lchild=s-rchild=NULL;s-prior=s-next=NULL;if(!p){T=s;}elseif(e.nump-data.num){p-lchild=s;}else{p-rchild=s;}return1;}coutThenumberhasbeenexisted!endl;return0;}intDeleteTree(BiTree&T,Typee){//递归算法，二叉排序树中元素删除intDelete(BiTree&);BiTreep;if(!T)return0;if(!SearchTree(T,e,p)){return0;}if(e.num==T-data.num){Delete(T);return1;}elseif(e.numT-data.num){DeleteTree(T-lchild,e);}else{DeleteTree(T-rchild,e);}return1;}intDelete(BiTree&p){//结点删除算法if(!p-lchild){//没有左孩子BiTreeq;q=p;p=p-rchild;free(q);}elseif(!p-rchild){//没有右孩子BiTreeq;q=p;p=p-lchild;free(q);}else{//两个孩子都有BiTreeq,s;q=p;s=p-lchild;while(s-rchild){q=s;s=s-rchild;}p-data.num=s-data.num;if(q!=