构造二叉树算法的研究

来源:用户上传      作者:

　　摘要：本文介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法。同时本文将给出基于先序序列和结点右孩子情况的构造二叉树的非递归的新算法。
　　关键词：构造二叉树；遍历序列；非递归算法
　　中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011) 13-0000-01
　　Research on the Construction A Binary Tree Algorithm
　　Shan Huiru
　　(Suzhou University,School of Computer Science and Technology,Suzhou215006,China)
　　Abstract:This article describes two kinds by the traversal of a binary tree or a sequence of node traversal sequences,and some information can uniquely identify the various possible ways the binary tree.This article will also be given based on the sequence and order situation of the right child nodes of non-recursive binary tree structure of the new algorithm.
　　Keywords:Binary tree structure;Traversal sequences;Non-recursive algorithm
　　一、二叉树的定义
　　二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于2。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。
　　在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树（不存在度大于2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i次方个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数（即叶子结点数）为n0，度为2的结点数为n2，则n0=n2+1。
　　二、算法的定义
　　算法（Algorithm）是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
　　三、递归算法的定义
　　递归是指某个函数或过程直接或间接的调用自身。一般地一个递归包括递归出口和递归体两部分，递归出口确定递归到何时结束，而递归体确定递归求解时的递推关系。递归算法有两个基本特征：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法，对于求解某些复杂问题，递归算法分析问题的方法是有效地；而是递归算法的时间、控件效率通常比较差。因此对解决某些问题时，我们希望用递归算法分析问题，用非递归算法解决问题，这就需要把递归算法转换为非递归算法。
　　四、递归算法与非递归算法的比较
　　递归的代码量比非递归的代码量少，因为非递归需要额外的变量记录当前所处的位置信息，以及额外的控制语句。而递归所使用的方式是函数调用，这是非常自然的栈结构，不需要记录位置信息，不需要添加控制语句，这些工作都由函数调用的特性解决了。
　　递归的执行效率比非递归的执行效率低，因为递归的实质是函数调用，而函数调用必然要进行线程栈空间的分配，记录每一次函数调用前的状态等工作，开销是比较大的。而非递归则不需要进行这些工作。
　　递归与非递归调用最主要区别就是在函数调用上。在计算机的工作方式中，函数调用是以栈结构来实现的，最早调用的函数处于栈底，最晚调用的函数处于栈顶，栈中存放的是每个函数中的局部变量等信息，当函数调用返回时该函数相关的信息就会从栈中弹出。
　　由此可以看出，递归每深入一层，栈的深度也会加一，而且当每一层的递归调用结束，都会自动返回上一层的递归中，因此不需要额外的变量记录当前所处的递归位置，也不需要while、if等控制语句进入或返回上一层或下一层递归。因此代码量比非递归的少。
　　五、算法的对比试验
　　我们的对比试验步骤如下：
　　Step1：随机生成一棵二叉排序树
　　Step2：得到这棵二叉排序树的先序序列和结点右孩子情况
　　Step3：将得到先序序列和结点右孩子情况分别传给两种算法
　　Step4：进行比较，显示结果
　　所谓二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：
　　1.若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　2.若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　3.左、右子树也分别为二叉排序树。
　　运行结果如下：
　　输入结点个数为1000时，新算法的时间消耗为0.370064，旧算法的时间消耗为0.396241；
　　输入结点个数为3000时，新算法的时间消耗为0.345599，旧算法的时间消耗为0.386879；
　　输入结点个数为4000时，新算法的时间消耗为0.342019，旧算法的时间消耗为0.396241；
　　输入结点个数为6000时，新算法的时间消耗为0.331142，旧算法的时间消耗为0.391621；
　　输入结点个数为8000时，新算法的时间消耗为0.343124，旧算法的时间消耗为0.386452。
　　本课题是构造二叉树算法的研究，主要任务是研究基于遍历序列构建二叉树的算法，设计一个基于二叉树的先序序列和结点的右孩子情况构造二叉树的非递归新算法。通过理论分析对比试验证明本文中的新算法，相对于旧算法而言，在效率方面表现更为出色，时间消耗较少。
　　本文的算法，仍有较大改进余地，鉴于新算法为非递归，所以循环的设计有待更一步的提高，进一步简化以减少算法运行时间和空间的消耗。
　　参考文献：
　　[1]Knuth D E.The art of computer programming,vol.1,fundamental algorithms[M].3rd ed.Reading,MA:Addison-Wesley,1997
　　[3]唐自立.基于遍历序列的唯一确定树或二叉树的方法[J].小型微型计算机系统,2001,22(8):985-988
　　

转载注明来源:https://www.xzbu.com/8/view-8724852.htm