二叉树的遍历研究及还原研究
摘要:通过对同一棵二叉树三种遍历方式的分析,概括出由前序、中序或由中序、后序遍历结果快速还原二叉树的方法。?
关键词:二叉树;二叉树的遍历;二叉排序树;还原? ?
二叉树是最为常用的数据结构,它的实际应用非常广泛。二叉树的遍历方式有三种,前序遍历、中序遍历、后序遍历。先序遍历的顺序为: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
(5)读入序列结束时,二叉树还原成功。还原后的二叉树如下图。?
(6)对于由中序序列和后序序列还原二叉树是,读入的序列为后序序列,从右向左读入,构造规则同上。还原结果与上述结果完全一致。?
-
倾听音乐、聆听音乐、静听音乐
音乐欣赏,是人的听觉器官接触音乐作品的音响运动形式而产生的一种能动的审美活动,也是一种通过音乐形象去体验和认识社会生活的积极的思维活动。通过音乐欣赏教学,可以接触古今中外的各种题材、体裁、风格的作品,从而开阔音乐视野,懂得一些基本的音乐知识,培养高尚的...
-
“多读”是语文教学的精髓
在文章中,不论是事情的记叙,人物和情境的描写,还是事物的介绍说明,观点的阐述和议论,都直接或间接,直露或含蓄地表达着作者的思想感情倾向,对学生起思想导航和激励作用,产生美感和丰富的想象,使学生不断地受到真善美的熏陶和感染。这在多数情况下都是通过朗读来实现的,忽...
-
供电企业班组员工绩效管理探讨
近年来,供电企业在不断创新与发展中,取得了不错的效益,随之而来的就是员工的绩效考核问题越发严重。为此,我们根据供电企业的特点,从整体方面对绩效考核探索出一个完善的考核模式。在现代信息社会,电成为了人们生活中必不可少的一部分,而供电企业也因为行业的增大而对...
-
浅议体育课多班同课窘境的应对策略论文
随着学校规模的不断扩大,在同一课次、同一场地上体育课的班级数也越来越多,而由于受场地、器材等因素的影响,造成了体育课多班同课教学的窘境。一、体育课多班同课教学窘境的原因1、体育设施配备滞后,同场教学有序开展受到制约。场地、器材配备与同课教学需求的差...