数据结构课程设计线索二叉树算法的实现

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

2、918014067 姓名： 穆闻 课程设计名称： 数据结构课程设计 设 计 题 目： 线索二叉树的实现 完 成 期 限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计内容：n 个结点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉树称为线索二叉树(threaded binarytree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前

3、驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。运用 vc+编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。要求:1） 阐述设计思想，画出流程图；2） 任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树；3） 说明测试方法，写出完整的运行结果；4） 从时间、空间对算法分析；5） 较好的界面设计；6） 编写课程设计报告。 以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查

4、合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘摘 要要这是一个关于线索二叉树的程序，该程序具有创建二叉树、遍历二叉树、线索化二叉树。其中，遍历和线索化都包含了先、中、后三种序列，而且对三种序列线索化后的二叉树也进行了遍历。该程序采用 vc 6.0 作为软件开发环境，采用 c 语言的各种语句和结构实现二叉树的一系列操作，并采用友好的界面向用户提供所操作的过程和数据状态，操作简单，界面清晰，易于被用户所接受。关键字：关键字：线索化；遍历；二叉树；先序；中序；后序目目 录录1 1

5、课题描述课题描述.12 2 任务分析任务分析.23 3 逻辑设计及描述逻辑设计及描述.33.1 二叉树的存储 .33.2 二叉树的遍历.43.3 二叉树的线索化.43.4 线索化二叉树的遍历.73.5 主函数 .104 4 程序编码程序编码.12总结总结.21参考文献参考文献.221 1 1 课题描述课题描述本程序重在设计二叉树的各种线索化实现，以 c 语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为：bithrtree createbitree()；/创建二叉树;bithrtree co

6、pybitree(bithrtree &rt)/复制一棵二叉树;void preordertraverse(bithrtree t)/先序遍历二叉树;void inordertraverse(bithrtree t) /中序遍历二叉树;void postordertraverse(bithrtree t)/后序遍历二叉树;bool preorderthreading(bithrtree &thrt, bithrtree t)/先序线索化二叉树;void prethreading(bithrtree p)/先序搜索结点的建立;bool inorderthreading(bithrtree &th

7、rt, bithrtree t)/中序线索化二叉树;void inthreading(bithrtree p)/中序搜索结点的建立;void backthreading(bithrtree p)/后序搜索结点的建立;bithrtree backorderthreading(bithrtree &rt)/后序线索化二叉树;bithrtree parent(bithrtree &thrt,bithrtree &p)/查找结点void preordertraverse_thr(bithrtree thrt)/遍历先序线索化二叉树;void inordertraverse_thr(bithrtree

8、thrt)/遍历中序线索化二叉树;void backordertraver(bithrtree thrt)/遍历后序线索化二叉树;void inorder_thr_t(bithrtree thrt,bithrtree &t)/将线索化后的二叉树还原;开发工具开发工具：c 语言运行环境运行环境：visual c+6.0。2 2 2 任务分析任务分析这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块流程图如图 2.1 所示。创建一棵二叉树递

9、归先序遍历递归中序遍历递归后序遍历先序线索化中序线索化后序线索化遍历先序线索化遍历中序线索化遍历后序线索化图 2.1 模块流程图3 3 3 逻辑设计及描述逻辑设计及描述3.13.1 二叉树的存储二叉树的存储1.1.创建二叉树（ createbitree(t)）设计思想：在用户需要创建二叉树时，屏幕提醒输入树的各个结点，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依次存放各结点。设计流程如图 3.1 所示。 beginych=#n y!(t=(bithrtree)malloc(sizeof(bithrnode)t=

10、nullreturn 0;return tcharch;t-data=ch;n 结束beginbithrtreetree;yrt=nullreturntree;!(tree=(bithrtree)malloc(sizeof(bithrnode)ytree-data=rt-data;return 0;tree=nulln结束n 图 3.1 createbitree(t ) 创建二叉树 图 3.2 copybitree(rt) 复制一棵二叉树2.2.复制二叉树（copybitree(rt)）设计思想：该函数的功能主要是为了避免前后两次的线索化混乱，其实质是重建二叉树以方便下一次的线索化。复制的方法

11、无外乎将各个结点拷贝至另一棵树，因为是完全一样的二叉树,所以连左右标志域也要一起复制,结点位置不能发生任何变化。设计流程如图 3.2所示，算法如算法 3.1 所示。bithrtree copybitree(bithrtree &rt) bithrtree tree;if(rt=null) tree=null; elseif(!(tree=(bithrtree)malloc(sizeof(bithrnode) return 0;tree-data=rt-data;/复制结点4 tree-ltag=rt-ltag;tree-rtag=rt-rtag;/复制左右标志域tree-lchild=copy

12、bitree(rt-lchild);tree-rchild=copybitree(rt-rchild);/复制左右孩子return tree;算法 3.13.23.2 二叉树的遍历二叉树的遍历1.1. 先、中、后遍历二叉树，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。设计流程如图3.3，主要算法如算法 3.2 所示。void preordertraverse(bithrtree t)/前序遍历 if (t!=nul

13、l)printf(%c ,t-data); /*访问根结点*/preordertraverse(t-lchild);preordertraverse(t-rchild); 算法 3.2 beginyt!=nullnprintf(%c ,t-data);preordertraverse(t-lchild)preordertraverse(t-rchild)结束 beginvoid prethreading(bithrtreep);y!tnthrt-lchild=t;thrt-lchild=thrt;prethreading(thrt)pre-rchild=thrt;pre-rtag=1;thrt

14、-rchild=pre;return 1;结束 图 3.3 preordertraverse(t)先序遍历二叉树 图 3.4 preorderthreading(thrt,t)先序线索化二叉树3.33.3 二叉树的线索化二叉树的线索化1.1. 先序线索化二叉树（preorderthreading(thrt,t)）设计思想：由于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针5 的过程，附设一个指针 pre 始终指向刚刚访问过的结点，若指针 p 指向当前结点，则 pre 指向他的前驱。由此可得先序遍历建立先序线索化的算法如算法 3

15、.3 和 3.4 所示。beginypny!p-lchildny!pre-rchildnp-lchild=pre;pre=p;pre-rchild=p;yp-ltag=0nyp-rtag=0nprethreading(p-lchile);prethreading(p-rchile);结束 beginypninthreading(p-lchild);y!p-lchildny!pre-rchildnpre=p;p-lchild=pre;pre-rchild=p;结束图 3.5 prethreading(p)先序搜索结点的建立图 3.6 inthreading(p)中序搜索结点的建立2 2中序搜索结

16、点的建立以及线索化如图 36 和 37 所示;后序搜索结点的建立和线索化如图38 和 39 所示。流程图不再多作说明。6 beginvoidinthreading(bithrtreep);!tnthrt-lchild=t;pre=thrt;inthreading(t);pre-rchild=thrt;pre-rtag=1;thrt-rchild=pre;结束y beginypnpostthreading(p-lchild);y!p-lchildny!pre-rchildnpre=p;p-ltag=1;pre-rtag=1;结束图 3.7 inorderthreading(thrt,t)中序线索

17、化二叉树图 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-lchild=thrt; /空二叉树 else thrt-lchild = t;pre =

18、thrt; /pre: 刚刚访问过的结点 prethreading(t);pre-rchild=thrt; pre-rtag=1;/最后一个结点线索化 thrt-rchild=pre; return 1; 算法 3.3 void prethreading(bithrtree p) if (p) 7 if(!p-lchild) p-lchild=pre; p-ltag=1; /前驱线索 if(!pre-rchild) pre-rchild=p;pre-rtag=1;/后继线索 pre = p;/保持 pre 指向 p 的前驱 if(p-ltag=0)prethreading(p-lchild);

19、 /左子树线索化 if(p-rtag =0)prethreading(p-rchild); /右子树线索化 /前序建立节点的搜索化算法 3.4beginbithrtreethrt;y!(thrt=(bithrtree)malloc(sizeof(bithrnode)nthrt-ltag=0;y!rtnreturn(thrt);thrt-lchild=rt;thrt-lchild=thrt;pre=thrt;postthreading(rt);thrt-rchild=pre;beginbithrtreetemp;temp-lchild=pnytemp=temp-lchild;temp-lchil

20、d!=p&temp-rchild!=pnreturntemp;y0=temp-rtagntemp=temp-lchild;ytemp=temp-rchild;结束 图 3.9 backorderthreading (thrt,t)后序线索化二叉树图 3.10 bithrtree parent(thrt,p)查找结点3.43.4 线索化二叉树的遍历线索化二叉树的遍历在程序设计中,实现线索化二叉树的遍历,实质上就是在查找每个结点的前驱和后继,而结点是否有前驱和后继、他们分别是什么,就要分情况去讨论。1.1.中序遍历线索化二叉树(inordertraverse_thr(thrt)时,结点的前驱应是遍

21、历左子树时访问的第一个结点,既左子树最左下方的结点,结点的后继应是遍历右子树时访问的第8 beginbithrtreep;p!=thrtnprintf(%c,p-data);p-ltag=0n(p-rtag=1)&(p-rchild!=thrt)nyp-ltag=0np=p-lchild;p=p-rchild;p=p-rchild;yyyp=p-lchild;结束 beginbithrtreep;p!=thrtnp-ltag=0nprintf(%c,p-data);(p-rtag=1)&(p-rchild!=thrt)np=p-rchild;p=p-rchild;yyp=p-lchild;y结

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

23、个结点。设计该函数的流程如图 313 所示。3.3.还原线索化二叉树(inorder_thr_t(thrt,t):涉及该函数的主要目的是在每次线索后9 beginbithrtreep;1np!=thrtn0=p-ltagny0=p-rtagnyprintf(%c,p-data);break;ythrt=parprintf(%cn,p-data);p=par-rchild|1=par-rtagpar-rtag=0p=par;par=par-rchild;par-ltag=0par=par-lchild;p=p-lchildp=p-rchildp=thrtp=paryyynnnyy结束n图 3.1

24、3 backordertraverse_thr(thrt) 遍历后序线索化二叉树10 都能清除掉前一次线索化过程中所留下的指针,因为不通顺序的线索化,其修改的空指针也不同,因此,进行下一次线索化前,必须还原空指针。此函数的流程如图 3.14 所示。beginbithrtreep,post;p!=thrtnp=thrt-rchild;p-ltag=0np-ltag=0;(p-rtag=1)&(p-rchild!=thrt)np=p-rchild;p-rtag=0;yp=p-lchild;yy结束 beginintc;c3ynreturnc;printf(n请选择需要执行的操作序列号:);结束 图

25、 3.14 inorder_thr_t (thrt,t)还原线索化后的二叉树图 3.15 menu_select()控制选择菜单3.53.5 主函数主函数1.1.主函数的设计流程如图 3.17 所示,在进行所需操作之前,屏幕会提示用户建立一棵二叉树,然后用空的 for 循环来控制不同操作之间的循环,用户选择序号 1,程序会自动执行二叉树的三种遍历,并输出遍历结果;用户选择 2,程序会自动执行二叉树的线索化操作,并打印出三种线索化后的结果。操作十11 分方便。beginbithrtreet,thrt,t;打印操作菜单nchoice=menu_select();choice=1n ynchoice

26、=2choice=3break;ybreak;printf(n已结束!谢谢使用!n);y后序postordertraverse(t);前序preordertraverse(t);中序inordertraverse(t);前序preorderthreading(thrt,t);还原inorder_thr_t(thrt,t);中序inorderthreading(thrt,t);后序backordertraver(thrt); 建立后序thrt=backorderthreading(t); 遍历线索化二叉树遍历二叉树结束图 3.17 main()主函数12 4 4 程序编码程序编码/-有关定义-#

27、include #include #include #include typedef struct bithrnode /线索二叉树中结点的定义 char data; int ltag,rtag; struct bithrnode *lchild,*rchild;bithrnode,*bithrtree;/-构建二叉树-bithrtree createbitree() char ch;bithrtree t; scanf(%c,&ch); /从键盘输入 ch； if(ch=#) t=null; /如果 ch=#,则 t 为空指针elseif(!(t=(bithrtree)malloc(size

28、of(bithrnode) return 0;t-data=ch;t-ltag=0;t-rtag=0; /线索标志赋初值 0t-lchild=createbitree();/先序建立 t-lchild;t-rchild=createbitree();/先序建立 t-rchild; return t; /返回树结点头指针 bithrtree copybitree(bithrtree &rt)/复制一棵二叉树bithrtree tree;if(rt=null) tree=null;elseif(!(tree=(bithrtree)malloc(sizeof(bithrnode) return 0;

29、tree-data=rt-data;tree-ltag=rt-ltag;tree-rtag=rt-rtag;tree-lchild=copybitree(rt-lchild);tree-rchild=copybitree(rt-rchild); return tree; /-递归遍历二叉树-void preordertraverse(bithrtree t)/先序遍历13 if (t!=null) printf(%c ,t-data); /*访问根结点*/ preordertraverse(t-lchild); preordertraverse(t-rchild);void inordertr

30、averse(bithrtree t) /中序遍历 if (t!=null) inordertraverse(t-lchild); printf(%c ,t-data); /*访问根结点*/ inordertraverse(t-rchild);void postordertraverse(bithrtree t) /后序遍历 if (t!=null) postordertraverse(t-lchild); postordertraverse(t-rchild); printf(%c ,t-data); /*访问根结点*/ /-线索化二叉树-bithrtree pre; /全局变量,刚刚访问过

31、的结点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-lchild=thrt; /空二叉树 else thrt-lchild = t; pre = thrt; /pre: 刚刚访问过的结点； prethreading(t); pre-rchild

32、=thrt; pre-rtag=1; thrt-rchild=pre; return 1; 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; if(p-ltag=0) prethreading(p-lchild); /左子树线索化 if(p-rtag =0) prethreading(p-rchild); /右子树线索化 /先序建立节点的搜索化bool inordert

33、hreading(bithrtree &thrt, bithrtree t)/中序线索二叉树 void inthreading(bithrtree p) ; thrt = (bithrtree)malloc(sizeof(bithrnode); /创建头结点 thrt-ltag=0; thrt-rtag=1; thrt-rchild=thrt;14 if (!t) thrt-lchild=thrt; /空二叉树 else thrt-lchild = t; pre = thrt; /pre: 刚刚访问过的结点； inthreading(t); pre-rchild=thrt; pre-rtag=

34、1; thrt-rchild=pre; return 1; void inthreading(bithrtree p) if (p) inthreading(p-lchild); /左子树线索化 if (!p-lchild)/前驱线索 p-lchild=pre; 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); backthrea

35、ding(p-rchild); if(!p-lchild) p-ltag=1;p-lchild=pre; /前驱线索 if(!pre-rchild) pre-rtag=1;pre-rchild=p;/后继线索 pre=p; /后序搜索化节点的建立bithrtree backorderthreading(bithrtree &rt) bithrtree thrt; if(!(thrt = (bithrtree) malloc (sizeof(bithrnode) exit(1);thrt-ltag= 0;thrt-rtag=1;/建头结点thrt-rchild=thrt;/右指针回指 if(!r

36、t) thrt-lchild=thrt; /若二叉树空，则左指针回指 else thrt-lchild=rt; pre=thrt; backthreading(rt); /后序遍历进行后序线索化 thrt-rchild=pre; /最后一个节点处理 return 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 & tem

37、p-rchild!=p ) if(0=temp-rtag) temp=temp-rchild;/结点有右结点，往右 else temp=temp-lchild; /如果结点没有右孩子，去左孩子，没有左孩子，去前驱 15 return temp; /-遍历线索化二叉树-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

38、,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 inordertraverse_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

39、) p = p-rchild; printf(%cn%c,p-data,p-data); p = p-rchild; /void backordertraver(bithrtree thrt) bithrtree p; bithrtree par; p=thrt-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 的双亲: i

40、f(thrt=par) p=thrt;/若 parent 是 thrt，即 p 是根结点，则无后继 else if(p=par-rchild|1=par-rtag) p=par; /若 p 是双亲的右孩子，或者是独生左孩子，则后继为双亲 else while(par-rtag=0) /若 p 是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。 par=par-rchild; while(par-ltag=0) par=par-lchild; p=par; printf(%cn,p-data); 16 /-将线索化后二叉树还原-void inorder_thr_t(bithrtr

41、ee 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-rchild!=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_se

42、lect()int c;doprintf(n 请选择需要执行的操作序列号:); scanf(%d,&c);while(c3);return c; /-主函数-void main()int choice; bithrtree t,thrt,t; /定义树 printf(请输入树的结点(#表示结点为空):n); t=createbitree(); /先序算法建立二叉树t=copybitree(t); printf(n); /复制一颗二叉树printf( 操作菜单 n);printf( n);printf( 1.遍历操作二叉树 n);printf( n);printf( 2.线索化二叉树 n);pr

43、intf( n);printf( 3.退出所有操作 n);printf( n);for(;)choice=menu_select();switch(choice)case 1:printf(n *遍历二叉树*n); printf(n 遍历二叉树结果:n);17 preordertraverse(t); 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 线索