线索二叉树的实现

1、数据结构课程设计设计说明书线索二叉树的实现学生姓名学号班级成绩指导教师曹记东计算机科学与技术系2010年9月10日数据结构课程设计评阅书题目线索二叉树的实现学生姓名学号指导教师评语及成绩指导教师签名：年 月日答辩评语及成绩答辩教师签名：年 月日教研室意见总成绩：室主任签名：年月日课程设计任务书2010 2011学年第1学期专业： 计算机科学与技术学号: 姓名： 课程设计名称：数据结构课程设计设计题目线索二叉树的实现完成期 限：自 2010 年8_月 30 日至 2010 年 9 月 10 日共 2 周 设计内容：n个结点的二叉链表中含有 n+1个空指针域。利用二叉链表中的空指针域，存放指向结点

2、在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索”）。这种加上了线索的二叉树称为线索二叉树（Threaded BinaryTree）。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称 为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。运用VC+编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求 用先左后右的递归或非递

3、归算法来实现。要求：1）阐述设计思想，画出流程图；2）任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树；3）说明测试方法，写出完整的运行结果；4）从时间、空间对算法分析；5）较好的界面设计；6）编写课程设计报告。以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）： 教研室主任（签字） ：批准日期：年 月 日摘要设计了一个对线索二叉树实现遍历的软件， 该软件可以实现对线索二叉树分别进行先序遍历、 中序遍历、 后序遍历 这种遍历方法是以线索为根本，

4、利用该软件，用户可以方便的查找树中任意结点的前驱和后继，给用户带来了方便。该 软件采用了 VC6.0 作为软件开发环境，实现对线索二叉树的遍历。操作简单，界面清晰，易于用户接受。关键词： 线索；先序遍历；中序遍历；后序遍历目录1 课题描述 12 设计过程 22.1 任务分析及课题分析 22.2 流程图 22.4 算法分析 112.5 测试结果 123 总 结 14参考文献 151 课题描述 本次课程设计的题目是线索二叉树的实现，该二叉树是以线索链表的存储方式来存储 的，该结点有五个域：数据域、左孩子、右孩子、前驱、后继，其中指向其前驱和后继的 指针叫做线索，这三种遍历（先序遍历、中序遍历、后序

5、遍历）是根据线索来遍历二叉树 的，对二叉树以某种次序的遍历使其成为线索二叉树的过程叫做线索化。由于线索化的实 质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结 点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过 程。12设计过程2.1任务分析及课题分析此任务设计了一个对线索二叉树进行先序遍历、中序遍历、后序遍历这三种遍历，先 序遍历是按（先根再左后右），中序遍历（先左再中后右），后序遍历（先左再右后中） 这种遍历方法是以线索为根本，该二叉树是以二叉链表为存储结构，在遍历的过程实质是 修改空指针的过程，把空指针改为指向结点前驱或后继的线索，

6、而一个结点的前驱或后继 结点的信息只有在遍历时才能得到。2.2流程图图2.1线索二叉树的实现总流程图-7 -图22先序遍历线索二叉树流程图开始图2.3中序遍历线索二叉树流程图图2.4后序遍历线索二叉树流程图开始P!=TNp=pre- rchildreturn OKp-ltag=link |p-rtag=li nk =2.3 程序实现代码#include#include#includetypedef enum PointerTaglink,thread; /link=0: 指针， thread=1 ：线索 / typedef struct BiThrNodechar data;BiThrNode

7、 *rchild, *lchild;PointerTag ltag,rtag;BiThrNode, *BiThrTree;BiThrTree CreateTree() /先序创建二叉树 /BiThrTree T;char ch;T=(BiThrNode *)malloc(sizeof(BiThrNode); ch=getchar();if( ch = # )T = NULL;elseT= ( BiThrTree )malloc( sizeof( BiThrNode ) );if( T)T-data = ch;T-ltag=link;T-rtag=link;T-lchild = CreateTr

8、ee(); / 创建左子树 /T-rchild= CreateTree(); / 创建右子树 /return T;BiThrTree pre;void preThreading(BiThrTree p)/先序线索化 /if(p)/ 访问根节点 /if(!p-lchild)p-ltag=thread; p-lchild=pre;if(!p-rchild)/右孩子为空p-rtag=thread;if(pre & pre-rtag=thread) pre-rchild=p;/结点存在且无右孩子pre=p;if(p-ltag=link)preThreading(p-lchild);/左子树存在，访问左

9、子树if(p-rtag=link)preThreading(p-rchild);/右子树存在，访问右子树BiThrTree preorderthreading(BiThrTree Thrt,BiThrTree T)/先序遍历二叉树 ,并将其先序线索化 /if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)/建立头结点 /exit(0);Thrt-ltag=link;Thrt-rtag=thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt; preThreading

10、(T);/ 先序遍历进行先序线索化 /pre-rchild=Thrt;pre-rtag=thread;Thrt-rchild=pre;return Thrt;void preTraverse(BiThrTree T)/先序遍历线索二叉树 /BiThrTree p;p=T-lchild;/指向左孩子 /printf(%c,p-data);while (p-rchild!=T)/ 根左右if (p-ltag=link) p=p-lchild;elsep=p-rchild; printf(%c,p-data);void midThreading(BiThrTree p)/ 中序线索化 /if(p)

11、midThreading(p-lchild); / 左子树线索化 / if(!p-lchild)p-ltag=thread; p-lchild=pre;if(!pre-rchild)pre-rtag=thread; pre-rchild=p;pre=p; midThreading(p-rchild); / 右子树线索化 /BiThrTree midorderthreading(BiThrTree &Thrt,BiThrTree T)/中序遍历，并将其中序线索化 /if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(0);Thrt-ltag=lin

12、k;Thrt-rtag=thread;- 13 -Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt; midThreading(T);pre-rchild=Thrt;pre-rtag=thread;Thrt-rchild=pre;return Thrt;/中序遍历进行中序线索化 /void midpreTraverse(BiThrTree T)/ 中序遍历线索二叉树 /BiThrTree p; p=T-lchild;while(p!=T)/ 空树或遍历结束时， P=T/while(p-ltag=link)p=p

13、-lchild;printf(%c,p-data);/ 访问左子树为空的节点 /while(p-rtag=thread&p-rchild!=T)p=p-rchild; printf(%c,p-data);p=p-rchild;void postThreading(BiThrTree p) if(p)postThreading(p-lchild);/后序线索化 /左子树线索化 /postThreading(p-rchild);if(!p-lchild) p-ltag=thread; p-lchild=pre;if(!pre-rchild) pre-rtag=thread; pre-rchild=

14、p;/ 右子树线索化 /pre=p;BiThrTree postorderthreading(BiThrTree &Thrt,BiThrTree T)/ 后序遍历，并将其后序线索化， / if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(0);Thrt-ltag=link;Thrt-rtag=thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt; postThreading(T); pre-rchild=Thrt; pre-rtag=thread; T

15、hrt-rchild=pre;return Thrt;/后序遍历进行后序线索化 /void postTraverse(BiThrTree T) /后序遍历后序线索化二叉树BiThrTree p; p=T; while(p-ltag=link|p-rtag=link) while(p-ltag=link) p=p-lchild;if(p-rtag=link) p=p-rchild;/有左孩子先访问左孩子 ,没有左孩子先访问右孩子/访问左孩子为空的结点的右孩子printf(%c,p-data); while(p!=T)/p 不为根结点if(p-rtag=link)/若 p 是有兄弟的左孩子if（p

16、re-rtag=thread|p=pre-rchild） / 若 p 是双亲的右孩子或是独生左孩子， 则后继为双亲 p=pre;elsep=pre-rchild;/后继为双亲的右子树上按照后序遍历访问的第一个结点。while(p-ltag=link|p-rtag=link)while(p-ltag=link) p=p-lchild;if(p-rtag=link)p=p-rchild;else/p 指向后继p=p-rchild;printf(%c,p-data);void main()/主函数 /BiThrTree T=NULL,pre;BiThrTree Thrt,p=0;int b;whil

17、e(1)printf（ 线索二叉树的实现 n）; printf（ 1. 先序遍历线索化二叉树 n）; printf（ 2. 中序遍历线索化二叉树 n）; printf( 3. 后序遍历线索二叉树 n); printf( 0. 退出程序 n);printf( 输入你的选择： ); scanf(%d,&b);switch(b)case 1:fflush(stdin); printf( 先序建立二叉树 :);T=CreateTree();printf( 先序遍历线索化二叉树 :); pre=preorderthreading(Thrt,T); preTraverse(pre);printf(n);b

18、reak;case 2:fflush(stdin);printf( 先序建立二叉树 :);T=CreateTree();printf( 中序遍历线索化二叉树 :); pre=midorderthreading(Thrt,T); midpreTraverse(pre);printf(n);break;case 3:fflush(stdin);printf( 先序建立二叉树 :);T=CreateTree();printf( 后序遍历线索化二叉树 :); pre=postorderthreading(Thrt,T); postTraverse(pre);printf(n);break;case 0

19、:printf( 退出程序 !);exit(0);break;2.4 算法分析遍 历二叉树的算法中的基本操作是访问结点，无论是按哪种次序进行遍历，对含有N个结点的二叉树，其时间复杂度均为 O (n),所需辅助空间微微遍历过程中栈的最大容量， 及树的深度，最坏情况下为n,则空间复杂度也为O (n)。若在程序中采用二叉树需经常遍 历或查找结点在遍历所得线性序列中的前驱和后继，则采用线索链表作存储结构。 X2.5测试结果调试和运行各个函数的结果如图2.6、2.7、2.8、2.9r FD觀序垃圾包Ddbu怎鼓盍二叉酎的咒现.OXC -15 -3利二二叉 现化化二-线线线珂予颅厉亠空二苗龙加历亠卑 民遍ifiM番丈历黒遍遍；!一 称薙劇二be仙环為MCWbitL-a二製化二B異素优践錢玻ff星;L&-FltMh中后退?.图2.6先序遍历线索二叉树运行结果r F：曜序垃圾包航bug鼓盍二叉时的寓现4尹MW 叉X料 二二X一一一二X:gs罢索: 择灭索的线线线择 鬪刃一力历玄二為历一力历竄 戛畳遍篇话历民曙遢籍 十虽中启退马U.E.0M花E.D.H.图2.7中序遍历线索二叉树运行结果-17 -Tl“ 稈序垃圾包Webug哦素二叉树的实观