基于遍历序列的构造严格二叉树的算法

人们已经提出了一些由一棵二叉树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该二叉树的算法.这些算法当然适用于严格二叉树.根据基于遍历序列的唯一确定严格二叉树的方法,提出了一些新的由一棵严格二叉树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该严格二叉树的算法,为构造严格二叉树提供了更多的途经.     

二叉树的遍历研究及应用

通过对同一棵二叉树的先序遍历、中序遍历、后序遍历得到三个不同序列的分析,概括出二叉树前、中、后序遍历序列间的关系,根据遍历序列,确定对应的二叉树。     

二叉树遍历研究及应用

通过对同一棵二叉树的先序遍历、中序遍历、后序遍历得到三个不同序列的分析，概括出二叉树前中后序遍历序列间的关系。     

二叉树构造算法解析

构造与遍历一棵二叉树历来为数据结构中不可缺少的内容。构造二叉树经典的算法通常都是以遍历二叉树为基础的,先决条件已知二叉树结点的左右孩子情况,或者是由先序和中序遍历序列、中序和后序遍历序列惟一确定一棵二叉树。通过对二叉树结构特点的分析,提出了三种不同的构造二叉树的算法,并加以分析。     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.     

基于遍历序列恢复二叉树的新解法及其证明

提出了一种基于前序和中序遍历序列恢复二叉树的解法,算法以数学公式形式呈现,反映了建树过程中相关数据变化的一般规律,具备数学上的引用透明性,由此能机械获得非递归程序和循环不变式,并进行了正确性证明.通过简单变换,获得了后序+中序、前序+后序恢复二叉树的可信算法.实验效果表明了该解法的有效性.     

支持可重构计算的满二叉树中序存储策略及快速遍历算法

通过对满二叉树顺序存储序列与中序序列之间解析关系的研究,推导与证明了完全二叉树的一些重要性质,给出了一种可快速访问的满二叉树中序序列存储方法并设计出相应的遍历算法。基于该方法,一颗具有N个结点的满二叉树中序序列仅需要线性时间复杂度O(N)即可遍历,相关计算过程可嵌入在可重构系统中形成可重构计算单元。还给出了算法的C++实现过程及可重构系统的设计方案。     

顺序存储二叉树的遍历及其应用研究

顺序存储二叉树非常适用于二叉树的树形接近于满二叉树时的处理.本文介绍了二叉树的顺序存储结构及其优点、二叉树的遍历方法、顺序存储二叉树的层次遍历和递归遍历算法,以及层次遍历算法的一些简单应用.     

基于二叉树的加密算法

提出了基于二叉树的加密算法,加密算法利用加密二叉树的树形对明文信息进行加密处理,同时还可以实现密钥的多方保存.解密算法利用二叉树遍历序列的性质,在不构造二叉树的情况下,直接利用二叉树的中序序列和前序序列对密文实现解密,降低了算法的空间复杂度.     

由先序序列和结点的左孩子情况构造严格二叉树的高效算法

提出一种新的由一棵严格二叉树的先序序列和结点的左孩子情况构造该严格二叉树的非递归算法.通过实例给出了新算法的执行过程,同时说明,与已有的等价递归算法相比,新算法的时间复杂性更低,而最差情况空间复杂性相同.     

顺序存储的满二叉树中序遍历的非递归算法

从中序遍历的定义出发以及满二叉树的自身特点出发，得出了关于顺序存储的满二叉树中序遍历的性质，从而推导出一种全新的、逻辑结构非常清晰的、与递归解完全等效的非递归、不需使用堆栈的算法，以及该算法在其他问题上的应用和推广。     

直序扩频通信中同步捕获的改进算法

提出一种用于直序扩频通信的同步捕获改进算法,其核心思想是让输入信号同时通过基本通带和辅助通带两个支路滤波器,经推导得出相应最优的中心频率和带宽.然后分别对两个支路的输出信号进行谱分析,通过比较两个支路输出信号的功率来判决本地PN码是否与输入信号的PN码同步,实现PN码同步捕获.仿真结果表明,该算法捕获性能良好、易于实现,适用于实际的扩频通信系统.     

GNSS软件接收机中匹配滤波器算法

为了适应全球卫星导航定位系统接收机的发展趋势,针对GNSS系统不同信号,研究了一种联合多个星座卫星信号的软件匹配滤波器捕获算法.通过对算法的分析,给出了影响算法复杂性的两个因素:接收序列伪码长度和本地复现序列数,并通过仿真给出了捕获GPS和伽利略开放信号可以使用的最佳复现序列数.仿真结果表明,对不同的GNSS信号,只要通过软件配置算法中的复现序列数,就可以以最小的计算复杂性来捕获相应信号.这对软件接收机中匹配捕获算法的设计有重要的指导意义.     

树非递归遍历统一的新解法及其形式证明

提出树遍历统一的新解法,使其非递归算法像递归算法一样简单.首先以后序遍历为例,基于结点状态标记和遍历规则提取,从遍历定义导出遍历的递推公式,由此机械获得非递归算法和循环不变式,并用形式化方法证明其正确性.之后按不同遍历定义变换公式参数,获得二叉树前序、中序和K叉树前序、后序的递推公式,所得算法比传统算法更简洁直观,表明本解法的有效性和通用性.     

用栈无标记变量后序遍历二叉树算法

给出一种用栈无标记变量后序遍历二叉树算法,并与常见的用栈加标记变量后序遍历二叉树算法就额外空间和额外栈深等进行分析比较.分析结果显示,无标记变量后序遍历二叉树算法可以节空间,降低复杂性.     

二叉树的顺序表存储

目前,对二叉树存储结构主要有顺序存储结构和链式存储结构(二叉链表)2种.其中顺序存储结构主要用于完全二叉树,而链式存储结构可用于所有的二叉树,是比较常用的存储结构.但是这种二叉链式存储结构由于叶子结点指针域不能被利用,存在大量的空指针而导致整个树存储密度低下.同时,应用这种二叉链式存储,对二叉树进行遍历、结点查询等操作时,需要用到显式或隐式栈,进而增加各种算法额外的空间,导致空间复杂度较高,而且各种操作过程也相对较复杂.为了提高二叉树的存储密度,降低各种处理算法的空间复杂度,简化对二叉树的遍历、结点查询、线索化等有关操作的具体实现过程,结合完全二叉树存储的思想,采用增加虚拟结点的方式对二叉树的实际结点编号,提出改进的二叉树存储结构——顺序表存储结构.     

一种新的简化ID3决策树的算法

决策树简化是决策树学习算法中的一个重要分支。文章以 ID3算法构造的决策树为基础 ,提出了一种高效的简化决策树的算法。算法先序遍历由 ID3构造出来的决策树的各个节点并对其子树进行比较 ,如果各子树的属性都相同而且存在某些相应的分支对于各子树完全相同 ,则改变决策树中相应属性的层次关系并把相同的分支分别合并起来。算法减少了决策树的深度、宽度与叶子数目 ,降低了决策树的规模。尤其对于逻辑表达式的归纳学习 ,简化之后的决策树要明显优于原决策树。     

一种新的树的遍历方法

树是一种非常重要的非线性的数据结构,对它的遍历一般有三种方法:先根序遍历、后根序遍历和按层次遍历.但在实际应用当中,我们可能需要不同于以上三种方法中的任何一种,这就要求我们对树的遍历不能仅仅有以上三种方法.提出了一种新的树的遍历方法,并且还给出了非递归算法的详细描述,以及算法的时间和空间的复杂度分析.     

GNSS站坐标序列速度和振幅变化的探测与分析

提出一种GNSS(global navigation satellite system)站坐标序列速度和振幅变化的探测算法.该算法根据二叉树原理遍历搜索所有可能发生变化的历元,并进行速度和振幅变化的建模分析,再采用F检验确定模型的显著性.模拟数据验证算法的正确性后,将该算法应用到中国地壳运动观测网络五个基准站的高程实测数据的探测与分析中,结果表明本文的模型相较于传统的时间序列拟合模型,拟合优度更高,更能反映数据的真实变化趋势与细部变化特征.     

递归算法非递归化的一般规律

尽管递归算法具有结构简练、清晰、可读性强、正确性容易得到证明等优点，但递归算法在执行过程中会耗费太多时间和空间。为了追求算法的时空效率，特别是使用不支持递归的程序语言的情况下，必须将递归算法转化为非递归算法，问题才能得到有效解决。为此，给出了递归算法转化为非递归算法的一般方法，并以Hanoi塔问题、二叉树的中序遍历问题为例进行了详细地分析。