由遍历序列确定二叉树的算法 被引量：4

1

作者 赵刚 李昆 《南昌航空大学学报（自然科学版）》 CAS 2010年第1期55-59,共5页

文章针对如何由二叉树的遍历序列来唯一确定二叉树的问题,提出了用两种遍历序列唯一确定一棵二叉树的方法。已知先序遍历和中序遍历或者已知后序遍历和中序遍历可以唯一确定一棵二叉树,但已知后序遍历和先序遍历就不能唯一确定了,只有... 文章针对如何由二叉树的遍历序列来唯一确定二叉树的问题,提出了用两种遍历序列唯一确定一棵二叉树的方法。已知先序遍历和中序遍历或者已知后序遍历和中序遍历可以唯一确定一棵二叉树,但已知后序遍历和先序遍历就不能唯一确定了,只有当要确定的树没有度为一的结点时,所确定的二叉树才是唯一的。对此文中给出了说明,并利用Turbo C实现了相应的算法。. 展开更多

关键词 先序遍历 中序遍历 后序遍历 二叉树

下载PDF 职称材料

由遍历序列构造二叉树的非递归算法实现 被引量：3

2

作者 刘璐 《衡水学院学报》 2009年第4期37-39,43,共4页

二叉树的构造有多种方法,给出一棵二叉树的中序序列和后序序列,可以构造出这棵二叉树,但一般采用递归算法.尽管递归算法具有结构简炼、清晰、可读性强等优点,但递归算法在执行过程会耗费太多的时间和空间,为了追求算法的时空效率,必须... 二叉树的构造有多种方法,给出一棵二叉树的中序序列和后序序列,可以构造出这棵二叉树,但一般采用递归算法.尽管递归算法具有结构简炼、清晰、可读性强等优点,但递归算法在执行过程会耗费太多的时间和空间,为了追求算法的时空效率,必须将递归算法转化为非递化算法,问题才能得到有效解决,本文设计了一个非递归算法,输入一棵二叉树的中序遍历和后序遍历的结点序列,构造出该二叉树,该算法对于一棵有n个结点的二叉树,具有O(n)时间复杂度,是解决该问题的最优算法. 展开更多

关键词 中序遍历 后序遍历 二叉树

下载PDF 职称材料

一种由层次遍历和其它遍历构造二叉树的新算法

3

作者 王防修 刘春红 《武汉轻工大学学报》 2016年第4期67-72,共6页

在由遍历序列构造二叉树问题的研究中,针对目前还没有用层次遍历和其它遍历一起构造二叉树的问题,提出了一种由层次遍历和其它遍历一起构造二叉树的新算法。考虑到层次遍历中左子树和右子树的层次遍历不具有递归属性,设计了从层次遍历... 在由遍历序列构造二叉树问题的研究中,针对目前还没有用层次遍历和其它遍历一起构造二叉树的问题,提出了一种由层次遍历和其它遍历一起构造二叉树的新算法。考虑到层次遍历中左子树和右子树的层次遍历不具有递归属性,设计了从层次遍历中分离出左右子树层次遍历的方法,并且通过组合得到具有递归属性的层次遍历。通过对层次遍历和中序遍历的递归属性的研究,设计了由层次遍历和中序遍历构造二叉树的递归算法;通过对层次遍历和先序遍历的递归属性的研究,设计了由层次遍历和中序遍历构造没有出度为1的二叉树的递归算法;通过对层次遍历和后序遍历的递归属性的研究,设计了由层次遍历和后序遍历构造没有出度为1的二叉树的递归算法。仿真结果表明,用设计的算法构造二叉树是有效的,可为二叉树的构造提供新算法。 展开更多

关键词 层次遍历 先序遍历 中序遍历 后序遍历 递归算法

下载PDF 职称材料

一种由遍历序列构造二叉树的改进算法 被引量：1

4

作者 王防修 刘春红 《武汉轻工大学学报》 2016年第3期68-73,共6页

针对现有构造二叉树的算法无法适用于具有相同元素的遍历序列,提出了一种解决该问题的递归算法。该种算法以现有的递归算法为基础,通过引入遍历序列的标志序列,依据标志序列中元素之间的关系,从理论上证明了三种由遍历序列构造二叉树的... 针对现有构造二叉树的算法无法适用于具有相同元素的遍历序列,提出了一种解决该问题的递归算法。该种算法以现有的递归算法为基础,通过引入遍历序列的标志序列,依据标志序列中元素之间的关系,从理论上证明了三种由遍历序列构造二叉树的算法都具有递归性。根据遍历序列构造二叉树的递归原理,设计了三种不同的由遍历序列构造二叉树的递归算法。通过算例仿真表明,使用笔者设计的算法可为具有相同元素的遍历序列构造二叉树。 展开更多

关键词 先序遍历 中序遍历 后序遍历 标志序列 递归算法

下载PDF 职称材料

基于二叉树的反向Hash链遍历 被引量：3

5

作者 傅建庆 吴春明 +1 位作者 吴吉义 平玲娣 《计算机研究与发展》 EI CSCD 北大核心 2012年第2期294-303,共10页

提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为... 提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为n的反向Hash链时,算法只需要存储[lbn]+1个节点值,并且进行不多于[(lbn-/2+1)n次Hash计算次数.相比同类其他算法,该算法并不要求链长为2的整数次方.通过对算法进行基于k叉树(k≥3)的扩展,进一步将存储空间降低到[lo gk[(k-1)n+1],但总计算次数提高到[(-logk[(k-1)n+1]-1)k/2+1]n;通过在算法执行前先把Hash链平分为p段(p≥2),将总计算次数降低到[(lb(n/p)-/2+1)n,但是所需的存储空间提高到[(lb(n/p)+1)p. 展开更多

关键词 反向Hash链 二叉树 K叉树 后序遍历 堆栈

下载PDF 职称材料

二叉树非递归周游算法

6

作者 李先 《阴山学刊》 1999年第5期55-57,共3页

本文给出了二叉树的一个非递归周游算法.二叉树采用三重链式存储结构,在算法过程中无须逆转链.

关键词 非递归周游算法 二叉树 前序周游 中序周游 后序周游 逻辑结构 三重链式 存储结构

下载PDF 职称材料

先序和后序序列恢复二叉树的非递归算法 被引量：1

7

作者 李昆 赵刚 《南昌航空大学学报（自然科学版）》 CAS 2010年第3期30-32,共3页

针对先序和后序序列不能唯一恢复一棵二叉树的问题,文章提出先序和后序序列在有些情况下是可以唯一恢复一棵二叉树的。即在结点的度只为0或2的二叉树中是可以由先序和后序序列唯一恢复的。对此文中给出了说明,并利用Visual C++6.0实现... 针对先序和后序序列不能唯一恢复一棵二叉树的问题,文章提出先序和后序序列在有些情况下是可以唯一恢复一棵二叉树的。即在结点的度只为0或2的二叉树中是可以由先序和后序序列唯一恢复的。对此文中给出了说明,并利用Visual C++6.0实现了相应的算法。 展开更多

关键词 非递归算法 二叉树 先序遍历 后序遍历

下载PDF 职称材料

树的后根遍历的一种并行算法 被引量：2

8

作者 熊家军 李庆华 张志祥 《小型微型计算机系统》 CSCD 北大核心 2002年第5期580-582,共3页

本文运用并行计算的 PRAM模型研究树的遍历问题 ,提出了树的后根遍历的一种并行算法 。

关键词 树 后根遍历 并行算法 数据结构

下载PDF 职称材料

由后序序列和结点的双亲情况构造严格二叉树的非递归算法 被引量：2

9

作者 唐自立 《南通职业大学学报》 2014年第4期93-98,共6页

提出一种新的由一棵严格二叉树的后序序列和结点的双亲情况构造该严格二叉树的非递归算法。通过实例说明该算法的执行过程,假设n是严格二叉树的结点的个数,该算法的时间复杂度和最差情况空间复杂度都是O(n)。

关键词 非递归算法 严格二叉树 后序序列 结点的双亲 严格二叉树构造

下载PDF 职称材料

由后序和中序遍历恢复二叉树的算法

10

作者 李昆 王卫华 《武汉理工大学学报（信息与管理工程版）》 CAS 2010年第6期910-913,共4页

针对如何由二叉树的遍历序列恢复二叉树的问题,提出了由后序遍历和中序遍历唯一确定一棵二叉树的算法,分别用递归和非递归两种方法进行了描述,并在Turbo C中实现了算法。

关键词 后序遍历 中序遍历 二叉树

下载PDF 职称材料

带危险度瓶颈限制的服务站截流选址-分配模型研究 被引量：1

11

作者 杨珺 杨超 吴云 《数学物理学报（A辑）》 CSCD 北大核心 2007年第5期955-960,共6页

该文考虑带危险度瓶颈限制的服务站截流选址-分配问题(FCLM).假设网络中各边有两个向量:长度和危险度.对于有一个起点和多个讫点的FCLM问题,网络的安全费用是一个关于可抵御最大危险度等级的非递减函数.该问题考虑如何选取可抵御最大危... 该文考虑带危险度瓶颈限制的服务站截流选址-分配问题(FCLM).假设网络中各边有两个向量:长度和危险度.对于有一个起点和多个讫点的FCLM问题,网络的安全费用是一个关于可抵御最大危险度等级的非递减函数.该问题考虑如何选取可抵御最大危险度的等级和服务站的位置使得建站费用和安全费用之和最小.文中建立了该问题的模型并提出了基于后序遍历的替代算法. 展开更多

关键词 选址 危险度 瓶颈 后序遍历

下载PDF 职称材料

后序遍历二叉树实现表达式求值 被引量：1

12

作者 潘凤 《山西师范大学学报（自然科学版）》 2015年第2期39-43,共5页

本文对中缀表达式进行扫描,借助链栈创建二叉树,后序遍历二叉树实现表达式求值.比传统表达式求值方法有着更高的时间和空间效率,尤其适用于同一表达式对于多种赋值组合求值的情况,如判定逻辑表达式的类型等,具有一定的实用价值.

关键词 中缀表达式 后序遍历 表达式求值

下载PDF 职称材料

基于后序遍历请求树的访问控制策略匹配算法 被引量：1

13

作者 边力 王炜 +2 位作者 姬瑞龙 王永强 郭睿志 《软件导刊》 2015年第12期58-62,共5页

为解决传统访问控制策略匹配算法中因产生大量无用路径而导致性能低下的问题,提出了一种改进的基于后序遍历请求树的策略匹配算法。该算法对请求树的节点进行后序遍历,并采用及时截止剪枝方法,避免了大量无用路径的产生,有效降低了匹配... 为解决传统访问控制策略匹配算法中因产生大量无用路径而导致性能低下的问题,提出了一种改进的基于后序遍历请求树的策略匹配算法。该算法对请求树的节点进行后序遍历,并采用及时截止剪枝方法,避免了大量无用路径的产生,有效降低了匹配输出结果大小,提高了策略匹配效率。实验证明,该算法较之传统的策略匹配算法大大提升了性能。 展开更多

关键词 策略匹配 后序遍历 访问控制

下载PDF 职称材料

由结点度的遍历序列确定二叉树的算法分析

14

作者 伍技祥 韩桂萍 《重庆文理学院学报（自然科学版）》 2008年第4期65-66,共2页

用二叉树的前序遍历、中序遍历、后序遍历的序列或结点度表示法都无法还原为唯一的一棵二叉树,中序遍历和结点度表示法二者结合组成一个序列,此序列也无法还原为唯一的一棵二叉树.但是用堆栈的方式可以将已知一棵二叉树包含结点度的后... 用二叉树的前序遍历、中序遍历、后序遍历的序列或结点度表示法都无法还原为唯一的一棵二叉树,中序遍历和结点度表示法二者结合组成一个序列,此序列也无法还原为唯一的一棵二叉树.但是用堆栈的方式可以将已知一棵二叉树包含结点度的后序遍历的序列还原为二叉树,而且此二叉树是唯一的. 展开更多

关键词 二叉树 结点度 后序遍历

下载PDF 职称材料

二叉树后序遍历的非递归算法 被引量：2

15

作者 黄霞 《现代计算机》 2009年第10期57-60,共4页

从示范二叉树的后序遍历入手,得出二叉树后序遍历递归算法的执行过程以及工作栈的变化情况,从中分析与总结,得出二叉树后序遍历的实质。从对二叉树后序遍历实质的进一步分析,得出两个特征,其一,当栈指针为空时,判断其是左子树还是右子树... 从示范二叉树的后序遍历入手,得出二叉树后序遍历递归算法的执行过程以及工作栈的变化情况,从中分析与总结,得出二叉树后序遍历的实质。从对二叉树后序遍历实质的进一步分析,得出两个特征,其一,当栈指针为空时,判断其是左子树还是右子树,来做出不同的处理;其二,从出栈结点是第一次出栈还是第二次出栈来决定是否访问该结点。从而得出二叉树后序遍历的两种非递归算法。最后,通过分析,对第二种算法再进行改进。 展开更多

关键词 二叉树后序遍历 栈 递归算法 非递归算法

下载PDF 职称材料

用于片上系统的二叉树快速遍历算法 被引量：2

16

作者 王兴波 《计算机工程与设计》 CSCD 北大核心 2013年第3期873-877,共5页

基于对满二叉树结点序号的研究,得到了满二叉树的层次结构、顺序序列与后序序列三者之间在数学上的对应关系,演绎出了满二叉树的层次结构及其顺序序列与后序序列之间互相转换的快速算法。算法可在常数时间内完成单个结点的查询、在线性... 基于对满二叉树结点序号的研究,得到了满二叉树的层次结构、顺序序列与后序序列三者之间在数学上的对应关系,演绎出了满二叉树的层次结构及其顺序序列与后序序列之间互相转换的快速算法。算法可在常数时间内完成单个结点的查询、在线性时间内完成整个序列的遍历。算法编码简洁,仅包含加、减、乘法与位运算,无递归调用无堆栈开销,几乎没有分支与跳转,不仅适合常规程序设计,而且适合于片上系统的专业开发。文中还指出了算法在机电设计方面的应用点。 展开更多

关键词 二叉树 非递归 后序遍历 片上系统 机电系统

下载PDF 职称材料

基于SIMD-SM模型的树的后根遍历并行算法 被引量：1

17

作者 熊家军 岳大为 李肯立 《计算机工程与应用》 CSCD 北大核心 2002年第6期98-100,共3页

文章基于SIMD-SM模型研究树的遍历问题,运用遍历树的边的思维方法,实现了树的后根遍历的一种并行算法,并且对该并行算法的复杂性进行了分析。

关键词 后根遍历 并行算法 树 SIMD-SM模型 数据结构

下载PDF 职称材料

基于EREW的后序遍历二叉树算法

18

作者 廖常武 《计算机工程与设计》 CSCD 北大核心 2006年第12期2285-2287,共3页

针对单处理器后序遍历二叉树的时间复杂度为O(n)问题,提出了在EREWPRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。... 针对单处理器后序遍历二叉树的时间复杂度为O(n)问题,提出了在EREWPRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。得出了运用该算法将时间复杂度从O(n)减少到O(logn)的结论。 展开更多

关键词 并行算法 后序遍历 二叉树 单链表 元素

下载PDF 职称材料

树的后根遍历的一种并行算法

19

作者 岳大为 熊家军 《空军雷达学院学报》 2001年第2期44-48,共5页

运用并行计算的ＰＲＡＭ模型研究树的遍历问题，提出了树的后根遍历的一种并行算法，并给出了一个实例。

关键词 后根遍历 并行算法 PRAM 并行计算 实例 模型研究

下载PDF 职称材料