线索化二叉树的实现.doc

《线索化二叉树的实现.doc》由会员分享，可在线阅读，更多相关《线索化二叉树的实现.doc（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计设计说明书线索二叉树算法的实现学生姓名XX学号XXXXXXX班级XXXXX成绩指导教师XXX计算机科学与技术系XXXX 年X月X日数据结构课程设计评阅书题 目线索二叉树算法的实现学生姓名XX学号XXXXXXX指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注: 指导老师成绩60%，答辩成绩40%，总成绩合成后按五级制计入。课程设计任务书20112012学年第1学期专业： 计算机科学与技术 学号： XXXXXXX 姓名： XXXX 课程设计名称： 数据结构课程设计 设 计 题 目： 线索二

2、叉树的实现 完 成 期 限：自2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计内容：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉树称为线索二叉树(ThreadedBinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质

3、的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。运用VC+编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。要求:1） 阐述设计思想，画出流程图；2） 任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树；3） 说明测试方法，写出完整的运行结果；4） 从时间、空间对算法分析；5） 较好的界面设计；6） 编写课程设计报告。 以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导

4、教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要这是一个关于线索二叉树的程序，该程序具有创建二叉树、遍历二叉树、线索化二叉树。其中，遍历和线索化都包含了先、中、后三种序列，而且对三种序列线索化后的二叉树也进行了遍历。该程序采用VC 6.0作为软件开发环境，采用C语言的各种语句和结构实现二叉树的一系列操作，并采用友好的界面向用户提供所操作的过程和数据状态，操作简单，界面清晰，易于被用户所接受。关键字：线索化；遍历；二叉树；先序；中序；后序目 录1 课题描述12 任务分析23 逻辑设计及描述33.1二叉树的存储33.2 二叉树的遍历43.3 二叉树的线索化43.4 线索化二叉树的

5、遍历73.5 主函数104 程序编码12总结21参考文献221 课题描述本程序重在设计二叉树的各种线索化实现，以C语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为：BiThrTree CreateBiTree()；/创建二叉树;BiThrTree CopyBiTree(BiThrTree &rt)/复制一棵二叉树;void PreOrderTraverse(BiThrTree T)/先序遍历二叉树;void InOrderTraverse(BiThrTree T) /中序遍历二叉树;voi

6、d PostOrderTraverse(BiThrTree T)/后序遍历二叉树;bool PreOrderThreading(BiThrTree &Thrt, BiThrTree T)/先序线索化二叉树;void PreThreading(BiThrTree p)/先序搜索结点的建立;bool InOrderThreading(BiThrTree &Thrt, BiThrTree T)/中序线索化二叉树;void InThreading(BiThrTree p)/中序搜索结点的建立;void backThreading(BiThrTree p)/后序搜索结点的建立;BiThrTree bac

7、korderThreading(BiThrTree &rt)/后序线索化二叉树;BiThrTree parent(BiThrTree &thrt,BiThrTree &p)/查找结点void PreOrderTraverse_Thr(BiThrTree Thrt)/遍历先序线索化二叉树;void InOrderTraverse_Thr(BiThrTree Thrt)/遍历中序线索化二叉树;void backorderTraver(BiThrTree Thrt)/遍历后序线索化二叉树;void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T)/将线索化后的二叉

8、树还原;开发工具：C语言运行环境：Visual c+6.0。2 任务分析这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块流程图如图2.1所示。图 2.1 模块流程图3 逻辑设计及描述3.1二叉树的存储1.创建二叉树（ CreateBiTree(T)）设计思想：在用户需要创建二叉树时，屏幕提醒输入树的各个结点，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依

9、次存放各结点。设计流程如图3.1所示。 图 3.1 CreateBiTree(T ) 创建二叉树 图 3.2 CopyBiTree(rt) 复制一棵二叉树2.复制二叉树（CopyBiTree(rt)）设计思想：该函数的功能主要是为了避免前后两次的线索化混乱，其实质是重建二叉树以方便下一次的线索化。复制的方法无外乎将各个结点拷贝至另一棵树，因为是完全一样的二叉树,所以连左右标志域也要一起复制,结点位置不能发生任何变化。设计流程如图3.2所示，算法如算法3.1所示。BiThrTree CopyBiTree(BiThrTree &rt) BiThrTree tree;if(rt=NULL) tree

10、=NULL; elseif(!(tree=(BiThrTree)malloc(sizeof(BiThrNode) return 0;tree-data=rt-data;/复制结点tree-LTag=rt-LTag;tree-RTag=rt-RTag;/复制左右标志域tree-lchild=CopyBiTree(rt-lchild);tree-rchild=CopyBiTree(rt-rchild);/复制左右孩子return tree;算法3.13.2 二叉树的遍历1. 先、中、后遍历二叉树，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该

11、函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。设计流程如图3.3，主要算法如算法3.2所示。void PreOrderTraverse(BiThrTree T)/前序遍历 if (T!=NULL)printf(%c ,T-data); /*访问根结点*/PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 算法3.2 图 3.3 PreOrderTraverse(T)先序遍历二叉树 图3.4 PreOrderThreading(Thrt,T)先序线索化二叉树3.

12、3 二叉树的线索化1. 先序线索化二叉树（PreOrderThreading(Thrt,T)）设计思想：由于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过程，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前结点，则pre指向他的前驱。由此可得先序遍历建立先序线索化的算法如算法3.3和3.4所示。 图 3.5 PreThreading(p)先序搜索结点的建立图3.6 InThreading(p)中序搜索结点的建立2中序搜索结点的建立以及线索化如图36和37所示;后序搜索结点的建立和线索化如图38和39所示。流程图

13、不再多作说明。 图 3.7 InOrderThreading(Thrt,T)中序线索化二叉树图3.8 backThreading(p)后序搜索结点的建立bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T)/前序线索化二叉树 void PreThreading(BiThrTree p);/先序遍历进行先序线索化 Thrt = (BiThrTree)malloc(sizeof(BiThrNode); Thrt-LTag=0; Thrt-RTag=1; /创建头结点 Thrt-rchild=Thrt;/右指针回指 if (!T) Thrt-lchil

14、d=Thrt; /空二叉树 else Thrt-lchild = T;pre = Thrt; /pre: 刚刚访问过的结点 PreThreading(T);pre-rchild=Thrt; pre-RTag=1;/最后一个结点线索化 Thrt-rchild=pre; return 1; 算法3.3 void PreThreading(BiThrTree p) if (p) if(!p-lchild) p-lchild=pre; p-LTag=1; /前驱线索 if(!pre-rchild) pre-rchild=p;pre-RTag=1;/后继线索 pre = p;/保持pre指向p的前驱 i

15、f(p-LTag=0)PreThreading(p-lchild); /左子树线索化 if(p-RTag =0)PreThreading(p-rchild); /右子树线索化 /前序建立节点的搜索化算法3.4 图3.9 backOrderThreading (Thrt,T)后序线索化二叉树图3.10 BiThrTree parent(thrt,p)查找结点3.4 线索化二叉树的遍历在程序设计中,实现线索化二叉树的遍历,实质上就是在查找每个结点的前驱和后继,而结点是否有前驱和后继、他们分别是什么,就要分情况去讨论。1.中序遍历线索化二叉树(InOrderTraverse_Thr(Thrt)时,结

16、点的前驱应是遍历左子树时访问的第一个结点,既左子树最左下方的结点,结点的后继应是遍历右子树时访问的第 图 3.11 PreOrderTraverse_Thr(Thrt)遍历先序线索化二叉树图 3.12 InOrderTraverse_Thr(Thrt)遍历中序线索化二叉树一个结点,既右子树最左下方的结点。二叉树最左下方的结点没有前驱，最右下方的结点没有后继。设计该函数的流程如图3.12所示。2.在后序线索树(PostOrderTraverse_Thr(Thrt)中找结点后继比较复杂，分三种情况（1）根结点没有后继；（2）若结点是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则后继为双亲；

17、（3）若结点是其双亲的左孩子且其双亲有右子树，则后继为其双亲的右子树上按后序遍历访问的第一个结点。设计该函数的流程如图313所示。3.还原线索化二叉树(InOrder_Thr_T(Thrt,T):涉及该函数的主要目的是在每次线索后图 3.13 backOrderTraverse_Thr(Thrt) 遍历后序线索化二叉树都能清除掉前一次线索化过程中所留下的指针,因为不通顺序的线索化,其修改的空指针也不同,因此,进行下一次线索化前,必须还原空指针。此函数的流程如图3.14所示。 图 3.14 InOrder_Thr_T (Thrt,T)还原线索化后的二叉树图3.15 menu_select()控制

18、选择菜单3.5 主函数1.主函数的设计流程如图3.17所示,在进行所需操作之前,屏幕会提示用户建立一棵二叉树,然后用空的for循环来控制不同操作之间的循环,用户选择序号1,程序会自动执行二叉树的三种遍历,并输出遍历结果;用户选择2,程序会自动执行二叉树的线索化操作,并打印出三种线索化后的结果。操作十分方便。图3.17 main()主函数4 程序编码/-有关定义-#include #include #include #include typedef struct BiThrNode /线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *

19、lchild,*rchild;BiThrNode,*BiThrTree;/-构建二叉树-BiThrTree CreateBiTree() char ch;BiThrTree T; scanf(%c,&ch); /从键盘输入ch； if(ch=#) T=NULL; /如果ch=#,则T为空指针elseif(!(T=(BiThrTree)malloc(sizeof(BiThrNode) return 0;T-data=ch;T-LTag=0;T-RTag=0; /线索标志赋初值0T-lchild=CreateBiTree();/先序建立T-lchild;T-rchild=CreateBiTree(

20、);/先序建立T-rchild; return T; /返回树结点头指针 BiThrTree CopyBiTree(BiThrTree &rt)/复制一棵二叉树BiThrTree tree;if(rt=NULL) tree=NULL;elseif(!(tree=(BiThrTree)malloc(sizeof(BiThrNode) return 0;tree-data=rt-data;tree-LTag=rt-LTag;tree-RTag=rt-RTag;tree-lchild=CopyBiTree(rt-lchild);tree-rchild=CopyBiTree(rt-rchild); r

21、eturn tree; /-递归遍历二叉树-void PreOrderTraverse(BiThrTree T)/先序遍历 if (T!=NULL) printf(%c ,T-data); /*访问根结点*/ PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild);void InOrderTraverse(BiThrTree T) /中序遍历 if (T!=NULL) InOrderTraverse(T-lchild); printf(%c ,T-data); /*访问根结点*/ InOrderTraverse(T-rchild);void

22、 PostOrderTraverse(BiThrTree T) /后序遍历 if (T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c ,T-data); /*访问根结点*/ /-线索化二叉树-BiThrTree pre; /全局变量,刚刚访问过的结点bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T)/先序线索二叉树 void PreThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeo

23、f(BiThrNode); /创建头结点 Thrt-LTag=0; Thrt-RTag=1; Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; /空二叉树 else Thrt-lchild = T; pre = Thrt; /pre: 刚刚访问过的结点； PreThreading(T); pre-rchild=Thrt; pre-RTag=1; Thrt-rchild=pre; return 1; void PreThreading(BiThrTree p) if (p) if (!p-lchild) p-lchild=pre;p-LTag=1; /前驱线

24、索 if (!pre-rchild) pre-rchild=p;pre-RTag=1; /后继线索 pre = p; if(p-LTag=0) PreThreading(p-lchild); /左子树线索化 if(p-RTag =0) PreThreading(p-rchild); /右子树线索化 /先序建立节点的搜索化bool InOrderThreading(BiThrTree &Thrt, BiThrTree T)/中序线索二叉树 void InThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeof(BiThrNode); /创建

25、头结点 Thrt-LTag=0; Thrt-RTag=1; Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; /空二叉树 else Thrt-lchild = T; pre = Thrt; /pre: 刚刚访问过的结点； InThreading(T); pre-rchild=Thrt; pre-RTag=1; Thrt-rchild=pre; return 1; void InThreading(BiThrTree p) if (p) InThreading(p-lchild); /左子树线索化 if (!p-lchild)/前驱线索 p-lchild=p

26、re; p-LTag=1; if (!pre-rchild)/后继线索 pre-rchild=p;pre-RTag=1; pre = p; InThreading(p-rchild); /右子树线索化void backThreading(BiThrTree p) if(p) backThreading(p-lchild); backThreading(p-rchild); if(!p-lchild) p-LTag=1;p-lchild=pre; /前驱线索 if(!pre-rchild) pre-RTag=1;pre-rchild=p;/后继线索 pre=p; /后序搜索化节点的建立BiThr

27、Tree backorderThreading(BiThrTree &rt) BiThrTree thrt; if(!(thrt = (BiThrTree) malloc (sizeof(BiThrNode) exit(1);thrt-LTag= 0;thrt-RTag=1;/建头结点thrt-rchild=thrt;/右指针回指 if(!rt) thrt-lchild=thrt; /若二叉树空，则左指针回指 else thrt-lchild=rt; pre=thrt; backThreading(rt); /后序遍历进行后序线索化 thrt-rchild=pre; /最后一个节点处理 ret

28、urn thrt;BiThrTree parent(BiThrTree &thrt,BiThrTree &p) BiThrTree temp; temp=thrt; if(temp-lchild=p) return temp;/父节点是头结点 else temp=temp-lchild; while( temp-lchild!=p & temp-rchild!=p ) if(0=temp-RTag) temp=temp-rchild;/结点有右结点，往右 else temp=temp-lchild; /如果结点没有右孩子，去左孩子，没有左孩子，去前驱 return temp; /-遍历线索化二

29、叉树-void PreOrderTraverse_Thr(BiThrTree Thrt)/Thrt:头结点/遍历先序线索化二叉树BiThrTree p; p=Thrt-lchild; while(p!=Thrt)printf(%c,p-data);/此树不空 while(p-LTag = 0) p=p-lchild; printf(%c,p-data); while(p-RTag=1)&(p-rchild!=Thrt) p = p-rchild; printf(%c,p-data); if(p-LTag=0) p=p-lchild; else p=p-rchild; /void InOrder

30、Traverse_Thr(BiThrTree Thrt)/Thrt:头结点/遍历中序线索化二叉树BiThrTree p; p=Thrt-lchild; while(p!=Thrt)while(p-LTag = 0) p=p-lchild;printf(%c,p-data); while(p-RTag=1)&(p-rchild!=Thrt) p = p-rchild; printf(%cn%c,p-data,p-data); p = p-rchild; /void backorderTraver(BiThrTree Thrt) BiThrTree p; BiThrTree par; p=Thrt

31、-lchild; while(1) while(0=p-LTag) p=p-lchild; if(0=p-RTag) p=p-rchild; /p指向第一个被访问的结点 else break; while(p!=Thrt) printf(%c,p-data); par=parent(Thrt,p);/parent是p的双亲: if(Thrt=par) p=Thrt;/若parent是thrt，即p是根结点，则无后继 else if(p=par-rchild|1=par-RTag) p=par; /若p是双亲的右孩子，或者是独生左孩子，则后继为双亲 else while(par-RTag=0)

32、/若p是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。 par=par-rchild; while(par-LTag=0) par=par-lchild; p=par; printf(%cn,p-data); /-将线索化后二叉树还原-void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T)BiThrTree p,post; p=Thrt-lchild; while(p!=Thrt)while(p-LTag = 0) p=p-lchild; p-LTag=0; p-lchild=NULL; while(p-RTag=1)&(p-rchil

33、d!=Thrt) p-RTag=0; post=p-rchild; p-rchild=NULL; p=post;p = p-rchild; p=Thrt-rchild; p-RTag=0; p-rchild=NULL; T=Thrt-lchild;free(Thrt);/-选择菜单-int menu_select()int c;doprintf(n请选择需要执行的操作序列号:); scanf(%d,&c);while(c3);return c; /-主函数-void main()int choice; BiThrTree T,Thrt,t; /定义树 printf(请输入树的结点(#表示结点为

34、空):n); T=CreateBiTree(); /先序算法建立二叉树t=CopyBiTree(T); printf(n); /复制一颗二叉树printf( 操作菜单 n);printf( n);printf( 1.遍历操作二叉树 n);printf( n);printf( 2.线索化二叉树 n);printf( n);printf( 3.退出所有操作 n);printf( n);for(;)choice=menu_select();switch(choice)case 1:printf(n *遍历二叉树*n); printf(n 遍历二叉树结果:n); PreOrderTraverse(T)

35、; printf(n); printf(n 遍历二叉树结果:n); InOrderTraverse(T); printf(n); printf(n 遍历二叉树结果:n); PostOrderTraverse(T); printf(nn);break;case 2:printf(n *线索二叉树*n); InOrderThreading(Thrt,T);/中序线索化 printf(n 线索化后的内容:n); InOrderTraverse_Thr(Thrt); /遍历中序线索化二叉树 printf(n); InOrder_Thr_T(Thrt,T);/还原 PreOrderThreading(T

36、hrt,T);/前序线索化 printf(n 线索化后的内容:n); PreOrderTraverse_Thr(Thrt);/遍历先序线索化二叉树 printf(n); printf(n 线索化后的内容:n);/后线索化 BiThrTree thrt; thrt=backorderThreading(t); /建立后序线索二叉树 backorderTraver(thrt); /遍历后序线索化二叉树break; case 3:printf(n 已结束!谢谢使用!n);exit(0); 5 程序调试与测试1.在程序调试正确后执行程序，会出现运行框显示“请输入树的结点(#表示结点为空)”的提示语，当准确输入二叉树后(空节点包括在内)，选择菜单分别执行用户所需要的操作,输入abc#d#ef#g#表示一棵如图5.1所示的二叉树 图 51二叉树结构图 图 52中序线索二叉树2.程序实际运行结果如图5.3所示:图5.3 创建二叉树3 .图5.4为整个程序的操作界面:图5.4 操作菜单界面 4.遍历二叉树理论的输出结果应为：先序遍历：a b c d e f g；中序遍历：c b d a f e g；后序遍历：c d b