没有合适的资源?快使用搜索试试~ 我知道了~
线索二叉树的应用.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 87 浏览量
2021-10-06
08:30:39
上传
评论 1
收藏 285KB DOC 举报
温馨提示
试读
34页
线索二叉树的应用.doc
资源推荐
资源详情
资源评论
- -
课程设计说明书
〔数据构造课程设计〕
专 业:网络工程
课程名称: 数据构造课程设计班级:网络B11-1
设计题目: 线索二叉树的应用
设计时间: 201 3 -2-25 至 201 3 -3-8
评语:_________________________________
_________________________________________
_________________________________________
_________________________________________
_________________________________________
评阅成绩:____评阅教师:__
- - word.zl-
- -
一、问题描述与需求分析
1、问题描述
本实验的问题是建立一个线索二叉树,并实现线索二叉树的插
入、删除、恢复线索等功能。
2、功能需求分析
本程序要实现的功能是: 1. 线索二叉树的建立。
2.线索二叉树的插入。
3.线索二叉树的删除。
4.线索二叉树的恢复。
想要完成上面的功能,我们首先是要知道上面是线索二叉树。
我们可以从数据构造的书上找到答案,利用二叉链表的空指针域将
空的左孩子指针域改为指向其前驱,空的右孩子指针域改为指向其
后继。这种改变指向的指针称为线索,加上了线索的二叉链表称为
线索链表。
N个结点的二叉链表中含有n+1个空指针域。利用二叉链表中
的空指针域,存放指向结点的在某种遍历次序下的前驱和后继结点
的指针,这种加上了线索的二叉链表称为线索链表。相应的二叉树
称为线线索二叉树。根据线索二叉树性质的不同,线索二叉树可以
分为前序线索二叉树,中序线索二叉树和后续线索二叉树三种,此
- - word.zl-
- -
次课程设计中使用的是中序线索二叉树。
二、概要设计
1、总体设计思路
首先就是要建立一个二叉树,然后再对二叉树进展线索化。
线索链表中的结点构造为:
其中:
- - word.zl-
- -
线索二叉树及其存储构造如
在线索树上进展遍历,只需先找到序列中的第一个结点,然后依次找结
点后继为空时而止。
以上图为例子说明在线索树中查找结点的后继。树中所有叶子的结点
是线索,那么右链域直接指示结点的后继,如结点 b 的后继为结点*。树中所有
非终端结点的右链均为指针,那么无法由此得到后继的信息。然而根据中序遍
历的规律可知,结点的后继应是遍历其右子树时访问的第一个结点,即右子树
最左下的结点。列入在找结点*的后继时,首先沿右指针找到其右子树的根结点
“—〞,然后顺其左指针往下直至其左标志为 1 的结点,即为结点* 的后继,在
图中是结点 c。反之,在中序结点中找结点前驱的规律是:假设其左标志为
“1〞,那么左链为线索,指示其前驱,否那么遍历左子树时最后访问的一个结
点〔左子树最右下的结点〕为其前驱。
- - word.zl-
- -
N N N N
Y Y Y Y Y
程序流程图
2、 模块简介
本程序有五个模块功能。每个模块功能均实现特定的功能。
1. 二叉树的建立:
中序输入二叉树,为程序提供数据,输入的时候空域用表示。
- - word.zl-
开场
定义二叉树
建立二叉树
选择菜单
输入 i(1--5)
I=1
I=2
I=4
I=5
I=3
中序输出二叉树
插入结点并线索化
删 除 结 点 并 线 索
haunted
输出线索二叉树
二叉树的线索化
完毕
剩余33页未读,继续阅读
资源评论
gjmm89
- 粉丝: 14
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功