完全二叉树总结点数与叶结点数关系分析

该文从两个角度分析了完全二叉树的总结点数与叶结点数之间的关系。其一,通过归纳找到总结点数的奇偶性与度为1的结点个数之间的关系,进而导出总结点数与叶结点数的关系;其二,由最后一个结点的父结点为倒数第一个分支结点的事实,找到总结点数与叶结点数的关系。这种多角度的分析有利于学生对此数据结构的深入理解。     

一种二叉树性质5的证明方法

二叉树的性质5说明完全二叉树中结点之间的关系可以通过对结点编号的简单算术运算得到,这意味着可以用线性结构表示这种非线性结构。为了明确和深入理解为什么完全二叉树结点之间的关系可以隐藏在线性的结点编号中,提出了一种简明的二叉树性质5的证明方法,并将证明思路应用于完全三叉树和完全m叉树,得到一个关于结点编号表示结点之间关系的一般性结论。     

分段式自适应确定BP网络隐层结点数——以遥感图像分类为例

隐层数和隐层结点数直接关乎BP网络的学习能力,但目前对隐层结点数的选择尚无适用的理论,一般凭经验或试凑确定.本文提出一种分段式自适应确定隐层结点数的算法,它通过评估网络输出相对误差相应调整隐层结点数,通过迭代运算在使网络输出相对误差逐步减小的同时,逼近可能的最优隐层结点数.通常这个最优结点数即网络输出相对误差出现震荡的起点对应的结点数,以这个结点数决定的网络结构能够在网络输出精度与运算开销之间取得较佳平衡.     

分段式自适应确定BP网络隐层结点数 ——以遥感图像分类为例

隐层数和隐层结点数直接关乎BP网络的学习能力，但目前对隐层结点数的选择尚无适用的理论，一般凭经验或试凑确定。本文提出一种分段式自适应确定隐层结点数的算法，它通过评估网络输出相对误差相应调整隐层结点数，通过迭代运算在使网络输出相对误差逐步减小的同时，逼近可能的最优隐层结点数。通常这个最优结点数即网络输出相对误差出现震荡的起点对应的结点数，以这个结点数决定的网络结构能够在网络输出精度与运算开销之间取得较佳平衡。     

从中序遍历及后序遍历构造二叉树

本文给出了一个算法，该算法输入一棵二叉树的中序遍历和后序遍历的结点序列，构造出该二叉树。该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数。     

遍历二叉树的一种改进算法

在计算机科学与工程中,二叉树是一类十分重要的数据结构,有着广泛的应用。本文介绍二叉树的主要操作:遍历二叉树,和遍历算法;对于后序遍历,提出一种新的改进的非递归算法。传统的后序遍历非递归算法,需要为二叉树的结点建立标志位,用以判断该结点是否应进行访问。标志位随同结点的指针一起存入栈中。标志位的使用无疑增加了存贮空间。我们提出的改进算法,无须为二叉树的结点建立标志位,从而节省了存贮空间,但并不增加算法的时间复杂度。算法中所采用的思想与技巧亦可以推广应用到一般树(多叉树)的遍历算法中。     

改进的多层栅格嵌入算法

本文提出的设计算法可以把厚度至多为是、结点数为。的图在O(。’)的面积内嵌入在活动层模型,并且可以使结点接任何预先指定的次序排成一行.此结果改进了Aggargal的 叶。勺嵌入面积m.本文还证明了存在一个结点数为。、度数为二的图,对于结点的某种排列,其平面嵌入面积的下界为 外。,).     

CSBTT:一种基于二叉树遍历的XML文档编码模式

XML文档数据编码模式是XML文档查询处理的基础, 好的文档编码模式有利于提高文档的查询效率. 为了解决XML数据查询效率低、支持动态更新等问题. 本文在二叉树遍历的编码基础上, 引入二叉树的三叉链表存储结构对XML文档结点进行编码. 该编码利用自然数作为编码序号, 因此编码长度较短; 引入结点双亲指针, 方便结点之间结构关系的判定, 结点采用三叉树链式存储, 方便文档的更新操作.     

二叉树后序遍历的非递归算法

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

基于结点间距离统计的无向无权图同构判别

按照同构图的定义判断两个图是否同构,最坏情况下其时间复杂度是O(N!),当结点数N比较大时,计算速度非常慢,针对该问题,提出一种通过统计结点间距离和按照距离分层,计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法,该算法可以给出两个图的结点间可能的对应关系.如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应,其时间复杂度仅为O(N4),否则,根据结点间可能的对应关系,避免遍历所有结点序号的交换,计算量可以成倍地下降.     

用可视化法建立二叉树实例

提出用可视化法建立二叉树实例的概念,并借用满二叉树顺序存储的特殊性来实现可视化,解决了该方法实现时所碰到的一些问题。     

最优二叉树的逆推调位启发式算法设计

针对构造有个带权叶子结点的最优二叉树提出一种新颖的启发式算法,该算法根据递推算法的逆推原理,利用结点位置的调动产生的权的变化值来决定节点在最优二叉树中的位置。该算法在使二叉树达到最优的运算过程中,完全区别于以往的哈夫曼算法。逆推调位算法步骤简明,速度迅捷,最后以举例的方式说明该算法的实效性。     

基于遍历序列的唯一确定树或二叉树的方法

基于遍历序列的唯一确定树或二叉树的方法既体现了树或二叉村的遍历序列的部分性质,又是建立树或二叉村的存储结构的主要依据,本文首先介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法,然后分别针对树、严格二叉树与雨季叉排序树加以介绍,本文比较全面的介绍了基于遍历离列的唯一确定树或二叉树的方法,进一步完善了树或二叉树的遍历序列的性质。     

Embedding a complete binary tree into the supercube

Consider a complete binary tree with 2ⁿ − 1 nodes and a supercube with the same number of nodes. We present a new embedding method to map the complete binary tree into the supercube with dilation 1. Our simple mapping method is quite competitive with the previous result.     

一种基于二叉树结构的入侵检测研究

提出以二叉树结构取代原有入侵检测系统采用的链表结构,旨在改进入侵规则的存储和模式匹配,提高检测速度。对Snort规则结构作了简要分析,详细阐述了以规则聚类思想构建二叉树结构的过程;同时,采用C4.5算法为二叉树每个规则集节点动态选择最显著的特征,并进行并行测试,实现性能优化。为了尽可能减少冗余比较和无效匹配,引入数字型的IntMatch串匹配算法,有效地提高了模式匹配速度和规则的访问速度。     

A tree search algorithm for the container loading problem

This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time.     

基于二元关系消减的概念格维护算法

针对有限空间下如何快速维护概念格的问题,提出一种消减形式背景中冗余二元关系的概念格维护算法。传统的算法删除冗余关系后需要重新构造概念格,这种方式较为费时。而所提算法能够在原始概念格的基础上直接调整得到新概念格的方法,可以处理任意位置的二元关系消减的情况。它采用自底向上广度优先方式遍历格节点,首先根据当前节点是否同时包含冗余关系对象和冗余关系属性,将当前节点分为受影响的节点和不变节点;然后根据当前节点与父子节点的外延和内涵的关系,再将受影响的节点细分为4类,即减对象节点、减属性节点、分割节点、删除节点;最后根据父子节点的类型更新边。实验结果表明,在一定程度上与传统算法相比,所提算法能够获得更好的时间性能。     

构造二叉树算法的研究

本文介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法。同时本文将给出基于先序序列和结点右孩子情况的构造二叉树的非递归的新算法。     

Pretty-printing of trees

A pleasing layout of printed tree structures is difficult to achieve automatically. The paper points out three main problems. First, the horizontal position of a node on the printed page depends on global consideration of the position of other nodes; secondly, the physical characteristics of printers require scanning the tree in left-to-right top-to-bottom sequence; finally, page overflow for wide trees must be handled. These problems are illustrated by analysing the shortcomings of a simple printing algorithm. A suitable general binary tree printing algorithm is presented and its adaptation to other types of trees is shown.