设为首页
收藏本站
切换到宽版
用户名
Email
自动登录
找回密码
密码
登录
立即注册
快捷导航
网站首页
大学课后答案
毕业设计
高中课后答案
初中课后答案
小学课后答案
赞助我们
搜索
搜索
热搜:
物理答案
英语答案
高数答案
线性代数
本版
帖子
答案家
»
论坛
›
毕业设计
›
物理|光学|声学|热学|力学
›
2018二叉树的遍历研究及还原研究
返回列表
查看:
1218
|
回复:
0
2018二叉树的遍历研究及还原研究
[复制链接]
4367035
4367035
当前离线
积分
41
1
主题
1
帖子
41
积分
幼儿园
幼儿园, 积分 41, 距离下一级还需 59 积分
幼儿园, 积分 41, 距离下一级还需 59 积分
积分
41
发消息
发表于 2018-8-22 23:10:26
|
显示全部楼层
|
阅读模式
摘要:通过对同一棵二叉树三种遍历方式的分析,概括出由前序、中序或由中序、后序遍历结果快速还原二叉树的方法。?
关键词:二叉树;二叉树的遍历;二叉排序树;还原? ?
二叉树是最为常用的数据结构,它的实际应用非常广泛。二叉树的遍历方式有三种,前序遍历、中序遍历、后序遍历。先序遍历的顺序为:NLR,即先根结点,然后左子树、右子树;中序遍历顺序为:LNR先左子树,然后根结点、右子树;后序遍历顺序为:LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历序列不能唯一确定一棵二叉树。?
二叉排序树对二叉树作了进一步的限定:根结点的权值大于(或小于)左子树中所有结点的权值;根结点的权值小于(或大于)其右子树中所有结点的权值。?
那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树?下面以二叉树的前序和中序遍历序列为基础,利用二叉排序树的性质,给出快速还原二叉树的方法。?
1由给定前序和中序序列或中序和后序序列还原二叉树的方法?
例:前序序列:ABDECFGH 中序序列:DEBACGFH (后序序列:EDBGHFCA)?
(1)给中序序列中的每个结点从小到大、从左到右赋以权值,如下:?
D(1)E(2)B(3)A(4)C(5)G(6)F(7)H(8)?
(2)还原时读入的序列为前序序列,从左到右依次读入序列中的各个结点值和相应的权值; ?
(3)由读入的序列,根据第1)步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点,其他结点分别为左右子树中的结点。设根结点为TT,权值为NN,当前读入结点为SS,权值为MM,若MM<NN,则将SS插入到TT的左子树中,否则将SS插入到TT的右子树中。?
(4)将SS插入到TT的左子树或右子树的过程中,仍然遵循3)中的规则,直至左子树或右子树为空时止。?
(5)读入序列结束时,二叉树还原成功。还原后的二叉树如下图。?
(6)对于由中序序列和后序序列还原二叉树是,读入的序列为后序序列,从右向左读入,构造规则同上。还原结果与上述结果完全一致。?
回复
举报
返回列表
高级模式
B
Color
Image
Link
Quote
Code
Smilies
您需要登录后才可以回帖
登录
|
立即注册
本版积分规则
发表回复
回帖后跳转到最后一页
CopyRight(c)2016 www.daanjia.com All Rights Reserved. 本站部份资源由网友发布上传提供,如果侵犯了您的版权,请来信告知,我们将在5个工作日内处理。
快速回复
返回顶部
返回列表