实验三全线索链表应用

1、-. z实验三全线索链表应用问题定义及需求分析1.1课题目的和任务问题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针ne*t。通过该结点构造全线索二叉链表。实验要求：设计一个全线索二叉链表的应用程序。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 /重新线索化后，需要输出前驱和后继的元素值概要设计2.1抽象数据类型需要定义一个全线索二叉树，该树中含有数据，左右孩子，以及分别指向前驱和后继的指针。通过前驱和后继指针，将建立的二叉树中序线索化，从而实现对数据更方便和快速的获取。2.2主程序流程及各模块之间的调用关系详细设计3.1存储构造实现typedef struct Type/数据类型构造体声明 float num;Type;typedef

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

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

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

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

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

8、到一样元素并返回它的前驱和后继 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& ne*t)/中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 BiTree B=T-ne*t; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T)/该点的前驱为T，说明它无前驱 ne*t.num=B-ne*t-data.num;

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

10、arched and print its prior and ne*t:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,ne*t);/全线索中序查找*个元素的前驱和后继 if(m=1)/前驱和后继均有的情形 coutThe prior of number e.num is prior.num,; coutand its ne*t is ne*t.num.endl; else if(m=2)/只有后继的情形 coutThe prior of number e.num is not e*isted,; coutand its ne*t is n

11、e*t.num.endl; else if(m=3)/只有前驱的情形 coutThe prior of number e.num is prior.num,; coutand its ne*t is not e*isted.endl; else/未找到该数的情形 coutThe number searched is not e*istedendl; return 1;7.2程序全部代码#include#includeusing namespace std;typedef struct Type/数据类型构造体声明 float num;Type;typedef struct BiTNode/二叉

12、排序树构造体声明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* ne*t;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-ne*t=NULL; return 1;int DestroyTree(BiTree& T)/递归销毁二叉排序树 if(T=NULL) r

13、eturn 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 InsertTree(BiTree& T, Type e)/二叉排序树中元素插入 BiT

14、ree 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-ne*t=NULL; if(!p)T=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutThe number has been e*isted!data.num) Delete(T); return 1; else if(e.numdata.num) Delet

15、eTree(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-rchild) q=s; s=s-rchild; p-data.num=s-data.num; i

16、f(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& ne*t)/中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 BiTree B=

17、T-ne*t; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T) ne*t.num=B-ne*t-data.num; return 2; else if(B-ne*t=T) prior.num=B-prior-data.num; return 3; else prior.num=B-prior-data.num; ne*t.num=B-ne*t-data.num; return 1; B=B-ne*t; return 0;int InOrderThreading(BiTree& Thrt,BiTree& T)/中序遍历二叉排序树T，并将其线索化,头

18、结点为Thrt void InThreading(BiTree& ,BiTree& ); if(!T)return 0; else Thrt=(BiTree)malloc(sizeof(BiTNode); Thrt-ne*t=Thrt-prior=NULL; BiTree pre; pre=Thrt; InThreading(T,pre); pre-ne*t=Thrt; Thrt-prior=pre; return 1;void InThreading(BiTree& T,BiTree& pre)/将结点线索化 if(T) InThreading(T-lchild,pre); if(T-pri

19、or=NULL)T-prior=pre; if(pre-ne*t=NULL)pre-ne*t=T; pre=T; InThreading(T-rchild,pre); const int InOrderThrPrint(BiTree Thrt)/中序线索遍历输出树 if(!Thrt) return 0; BiTree B=Thrt-ne*t; while(B!=Thrt) coutdata.numne*t; coutendl; return 1;const int SearchPN(BiTree Thrt,BiTree T)/利用全线索查找所需元素的前驱和后继 Type e,prior,ne*

20、t; int m; coutPlease input a number to be searched and print its prior and ne*t:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,ne*t);/全线索中序查找*个元素的前驱和后继 if(m=1) coutThe prior of number e.num is prior.num,; coutand its ne*t is ne*t.num.endl; else if(m=2) coutThe prior of number e.num is not e*isted,; coutand its ne*t is ne*t.num.endl; else if(m=3) coutThe prior of number e.num is prior.num,; coutand its ne*t is not e*isted.endl; else coutThe number searched is not e*istedne*t=T-prior=NULL; RemoveThr(T-lchild); RemoveThr(T-rchild); ret