全线索链表应用

1、实验三 全线索链表应用问题定义及需求分析1.1课题目的和任务问题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针next。通过该结点构造全线索二叉链表。实验要求：设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例1.2数据形式输入数据形式：通过键盘输入数据输入值的范围：输入值的范围均为float型，范围为1.2e-38至3.4e+38。 输出数据形式：输出到显示器。1.3程序功能将全线索作用于二叉排序树中，通过对其进行中序遍历线索化，实现通过线索搜索某个节点的前驱和后继，并且利用线索，实现对整个树中数据的中序

2、线索输出，并且能够在删除树中某个节点后，实现对该树的重新线索化。1.4测试数据7 /树中元素的个数5 2 7 1 3 6 8 /依次输入的树中元素值3 /需要输出前驱和后继的元素值7 /删除的元素值8 /重新线索化后，需要输出前驱和后继的元素值1. 概要设计2.1抽象数据类型需要定义一个全线索二叉树，该树中含有数据，左右孩子，以及分别指向前驱和后继的指针。通过前驱和后继指针，将建立的二叉树中序线索化，从而实现对数据更方便和快速的获取。2.2主程序流程及各模块之间的调用关系2. 详细设计3.1存储结构实现typedef struct Type/数据类型结构体声明 float num;Type;t

3、ypedef struct BiTNode/二叉树结构体声明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;3.2负责模块的伪码算法（1）int visit(Type e,BiTree T)/找到相同元素并返回它的前驱和后继 if(T-data =e) return 1; else return 0;（2）const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,

4、Type& next)/中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 B=T-next; while(B非空且不等于T) if(visit(e,B)/找到等于e的B结点值 if(B前驱等于T) next=B-next-data;/B只有后继 return 2; else if(B后继等于T) prior=B-prior-data;/B只有前驱 return 3; else/B前驱和后继都不等于T (prior,next)=(B-prior-data,B-next-data); return 1;/前驱和后继都存在 B=B-next; return 0;（3）const i

5、nt SearchPN(BiTree Thrt,BiTree T)/利用全线索查找所需元素的前驱和后继 cine;/输入要查找的元素m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1)输出前驱和后继 else if(m=2)前驱不存在，输出后继 else if(m=3)后继不存在，输出前驱 else查找失败，树中无该元素 return 1;3. 调试分析4.1问题分析与解决方法对于给定输入数，查找它的前驱和后继，需要考虑该数是否存在前驱和后继，如果没有前驱和后继，则需要输出不存在标志。利用线索指

6、针很容易进行判断，如果需要查找的元素的前驱是线索的头（线索的头是个空结点），那么该元素就不存在前驱，只存在后继；而如果需要查找的元素的后继是线索的头，那么它就不存在后继，只有前驱。因此通过if进行判断，就可以成功输出需要查询的元素的前驱和后继。4.2算法的时空分析在树中查找某个元素并输出该元素的前驱和后继的整个时间复杂度最多为，空间复杂度为。4.3算法的改进设想 全线索的应用主要是为了方便树的遍历，能够快速的访问某个节点的前驱和后继，因此可以考虑将线索应用于平衡二叉树上，从而进一步提高平衡二叉树获取数据的速度。4.4经验和体会 在整个程序的编写过程中，出现一个问题，如果是首次线索化，便可以通过

7、线索成功输出该树，但当删除某个节点后，再次进行线索化，然后利用线索输出该树就无法得到完整的树。后来经过调试发现，由于第一次的线索化，该树内的各个线索指针已被赋值，所以第二次线索化实际上是失败的，因此需要先对树进行去线索化操作（把线索指针指空）后，再对其进行线索化，这样才能输出正确的数据。 可见，程序各个模块之间的影响不容小觑，必须对程序各个模块的功能和影响有个整体的把握才不至于出现不合设想的错误。4. 使用说明按照操作提示，通过键盘输入数据即可。输入的节点数据可以为小数，但是数量数据必须为正整数。5. 测试结果（截屏）（1）前驱和后继都存在的数：（2）只存在前驱的数：（3）只存在后继的数：6.

8、 附录7.1个人负责模块的程序代码int visit(Type e,BiTree T)/找到相同元素并返回它的前驱和后继 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next)/中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prio

9、r=T)/该点的前驱为T，说明它无前驱 next.num=B-next-data.num; return 2; else if(B-next=T)/该点的后继为T，说明它无后继 prior.num=B-prior-data.num; return 3; else/该点既有前驱也有后继 prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;const int SearchPN(BiTree Thrt,BiTree T)/利用全线索查找所需元素的前驱和后继 Type e,prior,ne

10、xt; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1)/前驱和后继均有的情形 coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2)/只有后继的情形 coutThe prior of number

11、 e.num is not existed,; coutand its next is next.num.endl; else if(m=3)/只有前驱的情形 coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else/未找到该数的情形 coutThe number searched is not existedendl; return 1;7.2程序全部代码#include#includeusing namespace std;typedef struct Type/数据类型结

12、构体声明 float num;Type;typedef struct BiTNode/二叉排序树结构体声明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;int InitTree(BiTree& T,Type e)/创建二叉排序树 T=(BiTree)malloc(sizeof(BiTNode); if(!T)return 0; T-data.num=e.num; T-lchild=T-rchild=NULL; T-prior=T-next=NULL; return 1;int

13、DestroyTree(BiTree& T)/递归销毁二叉排序树 if(T=NULL) return 0; DestroyTree(T-lchild); DestroyTree(T-rchild); free(T); return 1;int SearchTree(BiTree T,Type key,BiTree& p)/非递归算法，搜索二叉排序树中元素 while(T) if(key.num=T-data.num)p=T;return 1; else if(key.numdata.num) p=T; T=T-lchild; else p=T; T=T-rchild; return 0;int

14、 InsertTree(BiTree& T, Type e)/二叉排序树中元素插入 BiTree p; if(!SearchTree(T,e,p) BiTree s; s=(BiTree)malloc(sizeof(BiTNode); s-data.num=e.num; s-lchild=s-rchild=NULL; s-prior=s-next=NULL; if(!p)T=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutThe number has been existed!data.num) Dele

15、te(T); return 1; else if(e.numdata.num) DeleteTree(T-lchild,e); elseDeleteTree(T-rchild,e); return 1;int Delete(BiTree& p)/结点删除算法 if(!p-lchild)/没有左孩子 BiTree q; q=p; p=p-rchild; free(q); else if(!p-rchild)/没有右孩子 BiTree q; q=p; p=p-lchild; free(q); else/两个孩子都有 BiTree q,s; q=p; s=p-lchild; while(s-rchi

16、ld) q=s; s=s-rchild; p-data.num=s-data.num; if(q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild; free(s); return 1;int visit(Type e,BiTree T)/找到相同元素并返回它的前驱和后继 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next

17、)/中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T) next.num=B-next-data.num; return 2; else if(B-next=T) prior.num=B-prior-data.num; return 3; else prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;int InOrderThreadin

18、g(BiTree& Thrt,BiTree& T)/中序遍历二叉排序树T，并将其线索化,头结点为Thrt void InThreading(BiTree& ,BiTree& ); if(!T)return 0; else Thrt=(BiTree)malloc(sizeof(BiTNode); Thrt-next=Thrt-prior=NULL; BiTree pre; pre=Thrt; InThreading(T,pre); pre-next=Thrt; Thrt-prior=pre; return 1;void InThreading(BiTree& T,BiTree& pre)/将结点

19、线索化 if(T) InThreading(T-lchild,pre); if(T-prior=NULL)T-prior=pre; if(pre-next=NULL)pre-next=T; pre=T; InThreading(T-rchild,pre); const int InOrderThrPrint(BiTree Thrt)/中序线索遍历输出树 if(!Thrt) return 0; BiTree B=Thrt-next; while(B!=Thrt) coutdata.numnext; coutendl; return 1;const int SearchPN(BiTree Thrt

20、,BiTree T)/利用全线索查找所需元素的前驱和后继 Type e,prior,next; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1) coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2) coutThe prior of number e.num is not existed,; coutand its next is next.num.endl; else if(m=3) coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else coutThe number searched is not existednext=T-prior=NULL; RemoveThr(T-lchild); RemoveThr(T-rchild); r