基于二叉树的位排序算法

利用二叉树的结构性质 ,给出了一个基于二叉树的位排序算法 (BBS算法 ) .并证明了 BBS算法是生成二叉树的这组数据按排序码升序的排序 ,最后 ,我们讨论了该算法的算法复杂性 .     

二叉树非递归周游算法

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

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

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

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

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

二叉树的顺序表存储

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

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

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

用抽象数据类型实现子与父/兄二叉树的建立算法

对二叉树的存储结构（称之为子与父／兄的存储结构）进行了描述，在此基础上给出了二叉树的算法。描述了栈的抽象数据类型，并以栈为辅助结构来实现子与父／兄二叉树的建立算法。该算法的执行时间与二叉树中的结点数成正比。     

中序遍历二叉树的算法实现

本文对二叉树的遍历过程进行了深入的分析,并给出了中序遍历二叉树的递归算法和非递归算法。对递归算法中的工作栈的执行过程做了分析;对非递归算法中的重点和难点做了深刻探讨。     

二叉树排序非递归算法推导及形式化证明

非线性数据结构递归问题非递归算法的循环不变式的开发一直是形式化开发的难点.研究二叉树类非递归算法的推导及形式化证明方法,对二叉树排序算法进行推导,得出非递归Apla(Abstract Programming Language)算法及其精确而简单的循环不变式,然后用Dijkstra-Gries标准程序证明法证明算法的正确性,最后使用PAR平台C++程序自动生成系统自动生成C++代码.实例的实验结果简化了算法程序的推导和证明过程,对递归问题非递归算法的循环不变式的探测具有一定的借鉴意义,而且对非线性数据结构算法程序的推导及形式化证明具有指导意义.     

一种MathML格式数学公式匹配算法

提出了一种基于MathML的数学公式匹配算法.根据数学公式的MathML标记编码得到其二叉树表示,依据规则库对树形结构和变量名作归一化处理,层次遍历二叉树得到二叉树的结构码.对于待匹配的两个数学公式,若它们的结构码相同,分别先序遍历相应的二叉树,若它们先序遍历序列相同,则分别中序遍历相应的二叉树,若它们中序遍历序列相同,那么这两个数学公式匹配,否则不匹配.实验结果表明,该算法既适用于结构相同的数学公式的匹配,也适用于语义相同的数学公式的匹配,且具有较高的准确率,是一种较实用的算法.     

多边形链式编码方式的改进及其编码方法

由于链式编码以每个区域为单位存储边界,相邻区域的边界被重复存储,所以通过索引机制来检查是否存在多余的多边形,从而避免相邻边界被重复保存。基于多边形拓扑关系的算法,对多边形图形链式编码方式提出了一种改进算法,采用二叉树编码、霍夫曼原理,将链式编码进行了重新编码并转换成可运算的多边形矢量编码,实现了多边形图形的叠置运算功能,同时提高了链式编码方式的数据压缩效率。     

一种改进的基于树路径匹配的网页结构相似度算法

提出一种改进的基于树路径匹配的网页结构相似度算法, 该算法定义了树路径的序列相似度和位置相似度, 找出网页的树路径集合, 通过网页间的最佳树路径匹配计算结构相似度. 实验结果表明, 用改进后的算法计算网页结构相似度比传统树路径匹配方法更符合实际, 更合理有效.     

在数据库上实现一种高效显示的任意树形结构

根据树形结构的显示特征和线索二叉树的访问顺序,提出了一种新的表结构用来保存树,并在此表结构的基础上提出了新的树形结构显示算法,同时给出了增减节点以及求某个节点的所有子孙节点的算法。     

基于形状特征分划分的树状区域匹配图像检索

提出了一种依据形状特征划分的树状区域匹配的图像检索算法,其思想是首先基于形状特征将图像发为若干给定浓度的树状关系区域,再结合所划分区域的结构关系及其颜色特征进行匹配检索。通过2个检索粗过滤条件,显著提高了检索响应速度,应用此算法,图像中对象的几何变换（移动、旋转、比例缩放）不会影响到查询结果,实验测试的结果表明,与一般的颜色直方图匹配算法相比,该算法大大提高了检索效率。     

Web文档知识树设计及实现

分析了Web文档的结构特征,并利用知识树快速高效等特征,设计了Web文档知识树;基于Web文档知识树结构,提出了构建Web文档知识树的构造算法、创建知识结点算法以及知识树访问算法.并对上述算法作了分析和评价,说明了这些算法对提高Web信息检索的准确率以及信息查找的速度是有益的.     

基于粗集的混合变量决策树构造算法研究

文章提出混合变量决策树结构,并在此基础上提出基于粗集理论的混合变量决策树构造算法RSH2,算法在每个结点选择尽可能少的属性明确划分尽可能多的实例,减小了决策树规模,且易于理解。将RSH2算法与ID3算法及基于粗集的单变量决策树算法HACRs进行实验比较,结果表明该算法有良好性能。     

关于一类新的整和图

整和图是标号图中的新概念,１９９４年由Ｈａｒａｒｙ引入。Ｃｈｅｎ给出了一类树为整和图,并猜测每一棵树都是整和图。利用粘和的方法证明了叉点距离至少为２的一类树为整和图,从而给出了一类新的整和图。     

一种树的存储结构

采用静态数组的方式给出树的一种存储结构,并给出这种存储结构下的几种常用运逄的Ｃ语言程序,这种存储结构避开了链式存储结构中链域个数不定的困难,容易用ＦｏｘＢＡＳＥ等关系型数据库来实现相应的运算,可以将二叉树与树统一起来处理。     

Nearest neighbor search algorithm for GBD tree spatial data structure

This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.     

Nearest neighbor search algorithm forGBD tree spatial data structure

： This paper describes the nearest neighbor （NN） search algorithm on the GBD（generalized BD） tree. The GBD tree is a spatial data structure suitable for two- or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its-successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.