【VC++开源代码栏目提醒】:网学会员为需要VC++开源代码的朋友们搜集整理了二叉树后序线索化 - 其它论文相关资料,希望对各位网友有所帮助!
目录 一、功能概述··········································································································· 2 二、总体设计··········································································································· 2 1、设计思路 ····································································································· 2 2、设计框架图 ································································································· 4 3、设计流程图 ································································································· 6 三、详细设计··········································································································· 7 1、主函数 ········································································································· 7 1功能描述 ······························································································ 7 2实现过程 ······························································································ 7 3 程序
代码 ····························································································· 7 2、建立一棵二叉树各结点 ·············································································· 8 1功能描述 ······························································································ 8 2算法描述 ······························································································ 8 3程序
代码 ······························································································ 8 3、对二叉树进行后序线索化 ········································································ 10 1功能描述 ···························································································· 10 2算法描述 ···························································································· 10 3程序
代码 ···························································································· 10 四、效果及存在问题 ······························································································ 11 1、主菜单界面 ································································································ 11 2、创建根结点 ······························································································· 12 3、创建各个结点左右孩子 ············································································ 13 4、输出二叉树各结点 ··················································································· 15 5、对二叉树后序线索化 ················································································ 15 6、存在的问题 ······························································································· 16 五、心得 ················································································································ 16 六、参考文献········································································································· 17 一、功能概述 本系统所实现的功能是采用二叉链表存储二叉树并按后序遍历对二叉树进行线索化处理。
本系统的二叉树构造简单无需知道其先序序列、中序序列或者后序序列任何一个二叉树的构造可由用户跟根系统提示输入二叉的各个结点构造完二叉树后可对二叉树进行后序线索化并输出该二叉树的后序序列。
进入本系统主菜单一是建立一个二叉树二是对二叉树进行后序线索化在构建二叉树时系统提示先创建二叉树根跟结点然后进入系统构建二叉树的子菜单该菜单会依次提示用户创建各个结点的左孩子和右孩子二叉树建立完成后自动返回主采单用户可选择对该二叉树进后序线索化。
二、总体设计 1、设计思路 为了得到一个棵线索二叉树可以利用某结点空的左指针域指出该结点在某种遍历序中的直接前驱结点的位置利用结点空的右指针域指出该结点在某种遍历序列中的直接后继结点的位置对于那些非空的指针域扔然存放指向该结点左、右孩子的指针。
在得到一棵线索二叉树之前我们必需先建立一个二叉树为了使系统使用的更方便更简易我定义一个构造二叉树的函数和几个生成左孩子和右孩子的函数在构造二叉树的函数中根据用户需要判断用户输入的要求不断调用左孩子或右孩子函数从而完成二叉树的建立。
比如用户要在X结点中生成一个左孩子则先判断X的左孩子是否为空不为空则提示左孩子已建立请重新输入并返回上层菜单若为空则申请一个新的结点空间并将X的左孩子指针指向新生成的结点。
建立好一棵二叉树后对其进行线索化处理以后序遍历为例在遍历的过程中依次判断某结点的左孩子或右孩子是否为空若不为空则将其标志域lbit或rbit置为1。
2、设计框架图 开始 输出一棵建立好的二叉树结构 建立一棵二叉树 对二叉树后序线索化 创建根结点bt 创建各结点的左孩子 创建各结点的右孩子 系统主菜单 输出二叉树的后序序列 结束 3、设计流程图 开始Made by:饶立平建立一棵二叉树BTREE btbtnull进行后序线索化BTREE btbtnullifbtnull对二叉树后序化 POSTREADT-lchild POSTREADT-rchildifT-lchildT-lbit1T-lchildpostif T-rchildT-rbit1if post post-rbit1post-rchildTpostTprintfdT-datawhiletop-1BTREE TqqSTACKtopint kifq-lchildnullifq-rchildnullqSTACKtop--top-1qBTREEmallocsizeofBTNodebt-lchildqTqSTACKtopTqBTREEmallocsizeofBTNodebt-rchildqTqSTACKtopT输出二叉树的结构printfdt dnibt-data ifbt-lchildnull outbtreebt-lchild ifbt-rchildnull outbtreebt-rchild建立根结点bttop-1STACKtopbtNYNK2NN结束输出后序序列YYY K1K3 K4二叉树后序线索化流程图08321224饶立平Goto start 三、详细设计 1、主函数 1功能描述 构造系统的主菜单界面有两个选项一是建立一个二叉树二是对二叉树进行后序线索化并用一些编程工具能支持的字符美化主界面。
2实现过程 通过printf语句来实现美化整个主界面输出的效果和主菜单的各个选项用switch语句来实现主菜单的选择事件的发生。
3程序
代码 void main int aj BTREE bt btnull start: printf ---------------------------------------------------------n printfn ┃★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★┃ printfn ┃ 【1】. 建立一棵二叉树 ┃ printfn ┃ 【2】. 二叉树后序线索化 ┃ printfn ┃ Made By : 08321224 饶立平 ┃ printfn ┃★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★┃n printf ---------------------------------------------------------n printf请选择 scanfdj switchj case 1: printf n printf┃输入二叉树的根结点: ┃n printf n printf请输入结点 scanfda btBTheadanullnull /建立二叉树根结点/ bttreebt /建立二叉树的各个结点/ goto start /返回主菜单/ case 2: ifbtnull printf n printf 二叉树不存在请重新建立二叉树。
n printf n else printf〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓n printf 二叉树后序序列如下 n printf n POSTREADbt /后序线索化二叉树/ printfn〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓n goto start /返回主菜单/ 2、建立一棵二叉树各结点 1功能描述 根据用户自己的输入首先建立二叉树的根结点然后根据二叉树的构造用户自己可随意输入各个结点的左孩子和右孩子直至整个二叉树构建完成。
2算法描述 通过自定义的BTREE BThead函数来建立用户输入的根结点之后用一个堆栈STACKtop来储存结点和一个whiletop-1循环来实现用户对各个结点的建立每建立一个结点储存在STACKtop中top1若要返回上一结点则只需top-1进行出栈操作便可。
这样便实现了随意构造某结点的左孩子和右孩子从而使得用户创建二叉树而不受限制。
3程序
代码 void bttreeBTREE bt int ktop-1 int bc0 STACKtopbt /头结点进栈/ whiletop-1 qSTACKtop /把栈顶结点元素赋值给q/ bq-data printf n printf ┃ ☆╭┐┌╮☆°· ┃n printf ┃ ╭┘└┘└╮∴°☆° 1.添加结点d的左孩子。
┃nb printf ┃ └┐┌┘—╮∴° 2.添加结点d的右孩子。
┃nb printf ┃ ╭┴——┤ ├╮ 3.返回上一个结点。
┃n printf ┃ │ │ │●° 4.二叉树已经建立完成。
┃n printf ┃ ╰┬——╯ │ ∴°· ┃n printf ┃ ☆ 9--9--/∴☆ ☆╭┐┌╮☆° ┃n printf n printf请选择 scanfdk switchk case 1: ifq-lchildnull printfn printf 结点d已经有了左孩子请重新选择。
nb printfn else printf n printf┃输入结点d的左孩子结点┃nb printf请输入: scanfdc TBTlchildqc /建立左孩子结点T/ STACKtopT /左孩子结点进栈/ break case 2: ifq-rchildnull printfn printf 结点d已经有了右孩子请重新选择。
nb printfn else printf n printf┃输入结点d的右孩子结点┃nb printf请输入: scanfdc TBTrchildqc /建立右孩子结点T/ STACKtopT /右孩子结点进栈/ break case 3:qSTACKtop--break /最后一个结点出栈/ case 4:top-1break /清空堆栈/ printf-------------------------------------------n printf二叉树已经建立完成如下所示n printf n printf numbertdata n outbtreebt /输出二叉树的结点/ 3、对二叉树进行后序线索化 1功能描述 用户建立好一个完整的二叉树后为了使二叉树的遍历操作提供了更多的方便而且不需要设置堆栈将左右孩子不为空的标志域lbit或rbit置为1。
2算法描述 通过利用二叉树的二叉链表结构中的那些空的指针域来指出二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么 用递归构造一个后序遍历方式实现线索化的函数依次判断某结点的左孩子或右孩子是否为空若不为空则将其标志域lbit或rbit置为1。
3程序
代码 BTREE post void POSTREADBTREE T ifT POSTREADT-lchild /递归线索左子树/ POSTREADT-rchild /递归线索右子树/ ifT-lchild T-lbit1 /T的标志域置为1/ T-lchildpost if T-rchild T-rbit1 /T的标志域置为1/ if post post-rbit1 post-rchildT postT printf dT-data /输出访问的结点/ 四、效果及存在问题 1、主菜单界面 如图4-1.1所示以构造一棵图示的二叉树为例建立二叉树后输出该二叉树的各个结点对其进行后序线索化并以后序序列的形式输出。
图4-1.1 2、创建根结点 1 2 3 4 5 7 6 8 3、创建各个结点左右孩子 图4-3.1建立根结点1的左孩子结点2. 图4-3.2建立结点2的右孩子结点5. 图4-3.3返回结点5的上一个结点2. 根据系统提示可分别建立各个结点的左右孩子结点直至一棵二叉树建立完成。
由于该二叉树的结数比较多在此不一一列出各结点的建立过程。
4、输出二叉树各结点 5、对二叉树后序线索化 6、存在的问题 本系统虽然可以成功运行也能实现课题要求的各个功能但是因为时间原因部分细节问题还没有有效的解决。
一是在输出二叉树各个结点的时候编号没有递增显示二是我一直在构造一个在输出二叉数的各个结点时可以显示各结点的左右孩子结点的数据我分别用了一个q-lchild-data和q-rchild-data来显示孩子结点存放的数据但是当某结点左右孩子为空时则系统会出错在这个问题上浪费了较多的时间只好舍去了。
五、心得 通过本次《数据结构》课程设计使我对二叉树后序线索化的原理有了较为清楚的理解可以解释原来不懂的程序对于各种函数的调用也有了很好的掌握对C语言程序设计也有了一定的提高。
在拿到这个课题之前老师就交待过不能抄袭网上的程序于是在接到二叉树线索化这个课题后我便将书上二叉那张从头又看了一遍第一个闪过的念头就是我想做一个可以由用户自己根据二叉树的构造随意建立个各个结点直至整个二叉树构造完成。
也就是说可以不用根据该二叉树的前、中、后序序列来构造二叉树只需用户根据系统提示依次建立各个结点的左右孩子便可。
在程序设计中也碰到了很多的问题有时候运行时不免会遇到很多语法错误最终都算是一一调试成功我是在c的环境下用c语言来进行编程在c和c中都能正常运行只是因为c不技持中文和部分字符的显示。
以致程序运行时会出现乱码。
可以说在本次《数据结构》课程设计中我是受益非浅啊看着自己做好的程序不由自喜一把对于c语言的运用和
VC的编程软件掌握更上了一个台阶我会继续加油努力的 六、参考文献 数据结构教程第二版 唐发根 编著 北京航空航天大学出版社 C语言程序设计 夏涛 编著 北京邮电大学出版社
上一篇:
EVE模拟服务端编译搭建教程(上)
下一篇:
科研管理杂志简介