二叉树搜索（共7篇）
二叉树搜索 篇1
递归是软件设计中一种重要的方法和技术。满足递归要素的问题具有三个特征:⑴原问题具有某种可借用类同自身的子问题描述的性质;⑵子问题相对于原问题有进一步的简化;⑶某一有限步的子问题有直接解存在[1]。在问题的求解方法具有递归特征时, 采用递归技术具有较高的开发效率, 所设计的程序具有良好的可读性和可维护性。但在实际应用中, 递归过程用到的大量数据均需保存, 其算法的时间复杂度较高 (以计算斐波那契数列为例T (n) =O (2n) [2]) , 这样当递归层次多到一定程度, 将耗尽系统内存资源, 因此递归算法的实用性较差。另外, 有的程序设计语言并不支持递归设计机制, 为此, 需要研究同递归函数功能等价的非递归算法。
本文将重点分析搜索二叉树中最长路径的递归算法, 同时给出其C语言描述;介绍对该算法进行递归消解的具体方法, 并给出C语言非递归模拟算法, 最后对递归消解前后算法的时间效率进行分析。
1 递归过程的实现
递归函数的运行过程类似于多个函数的嵌套调用, 只是调用函数和被调用函数是同一个函数, 因此, 和每次调用相关的一个重要的概念是递归函数运行的“层次”[3]。
递归进层 (i→i+1层) 系统需要做三件事:
(1) 保留本层参数与返回地址 (将所有的实在参数、返回地址等信息传递给被调用函数保存) ;
(2) 给下层参数赋值 (为被调用函数的局部变量分配存储区) ;
(3) 将程序转移到被调用函数的入口。
而从被调用函数返回调用函数之前, 递归退层 (i+1→i层) 系统也要做三件事:
(1) 保存被调用函数的计算结果;
(2) 恢复上层参数 (释放被调用函数的数据区) ;
(3) 根据被调用函数保存的返回地址, 将控制转移回调用函数[4]。
递归函数的调用和返回过程满足“后调用先返回”的原则, 因此支持递归的程序设计语言系统其递归函数的数据区应设计成堆栈形式[1,3,4]。
2 递归消解
递归消解的方法根据递归算法中递归调用语句的结构以及所处位置的不同可分为两大类。一类是简单递归问题的递归消解方法;另一类是复杂递归问题的递归消解。
尾递归和单向递归都属于简单递归。尾递归指递归调用语句只有一条且处于算法的最后[4] (比如求n!的算法) 。单向递归指递归调用语句只和上层的主调函数有关, 相互间参数无关, 并且这些递归调用语句也和尾递归一样处于算法的最后[4] (比如计算斐波那契数列的递归算法) 。这类递归形式的算法可转化成直线型的规律重复问题, 即利用循环结构算法实现递归向非递归算法的转化。复杂递归问题的递归消解可利用堆栈模拟实现。
2.1 输出二叉树中最长路径的递归算法
设定二叉树采用二叉链表存储结构 (见图1) , 并通过指针root访问。
可用C语言定义如下:
该算法的递归设计思路如下:
1) 若二叉树为空, 输出空序列, 算法结束;
2) 否则, 输出根结点元素值, 并求根结点的左右子树的深度, 继续执行第⑶步;
3) 根据第⑵步求得的左右子树深度, 选择深度大的一棵子树, 从其根结点开始求最长路径。
假设树中结点的元素值为字符型, 即前述抽象数据类型DataType为char类型, 则该递归算法的C语言描述如下:
其中, 求解二叉树深度的递归算法思想可以描述如下:
1) 若二叉树为空, 则深度为0;
2) 否则其深度应为根结点的左右子树的深度的最大值加1[4,5]。
其C语言描述的递归算法如下:
2.2 求解二叉树深度算法的非递归模拟
首先, 求二叉树深度的递归算法是采用后序遍历过程实现的。
在后序遍历二叉树的过程中, 对一个结点的操作要两次经过该结点:第一次是由该结点找到其左孩子结点, 遍历其左子树后返回该结点;第二次是由该结点找到其右孩子结点, 遍历其右子树后再次返回该结点, 最后“访问”该结点。因此, 用非递归方法实现后序遍历求二叉树深度时, 需要设置一个栈结构, 用来保存指向所经历结点的指针。由于后序遍历二叉树时结点指针要进出栈各两次, 第二次出栈后才进行结点的相关操作, 因此需给进栈结点同时设置一个标志flag, flag=1代表结点第一次出栈, flag=2代表结点第二次出栈, 此时可执行该结点的“访问”操作[1]。
综上分析, 该算法中的辅助堆栈可定义如下:
初始设定栈顶为0表示空栈, 则二叉树的层次应为栈顶可能达到的最大值, 在算法执行过程中的结点第二次进栈时记录其所在层次即可。则非递归模拟算法可用C语言描述如下:
2.3 输出最长路径算法的递归消解
输出二叉树中最长路径的递归算法属于尾递归的简单递归算法, 因此可以利用循环结构消解递归。其非递归模拟算法可用C语言描述如下:
2.4 递归消解前后算法时间复杂度分析
评价算法的一个主要方面是其渐进时间复杂度 (简称时间复杂度, 记作T (n) =O (f (n) ) ) , 它同算法中语句的语句频度 (算法中语句的执行次数) 函数成等比例增长关系。通常时间复杂度以基本语句 (能够作为基本语句的一般为循环的最内层) 的语句频度函数的最高阶作为衡量依据, 表明该算法的执行时间随着问题规模n的增大的一种变化趋势。时间复杂度是衡量该算法的时间效率的一种重要依据, 时间复杂度越高, 算法的时间效率就越差[2]。
2.4.1 递归算法时间复杂度分析
递归算法的函数体中不存在循环语句, 但某次递归调用计算出的结果没有保存, 下一次用到时还需要重新递归计算, 这就导致递归函数的时间复杂度实际取决于递归函数自身调用的次数[2]。
PostTreeDepth函数求二叉树的深度, 不失一般性, 可根据图示二叉树存储结构分析其调用次数 (见图2) 。
从图2中看出:首次调用从根结点A开始, if语句条件为真, 递归调用A的左孩子结点B, 同样if条件为真, 继续递归调用B结点的左孩子结点D, 在调用D结点的左孩子结点时if语句条件为假, 向上层调用 (结点D的调用) 返回0值, 接着再对D结点的右孩子进行递归调用, 同样if语句条件为假返回0值, 从而结点D的调用返回1给其上层调用 (结点B的调用) , 然后再对B结点的右孩子进行递归调用, ……。以此类推, 该递归调用总次数实际是对应二叉树中结点以及空指针的总个数。有n个结点的二叉链表中有n+1个空指针, 则递归调用总次数为2n+1次。
SearchLongestPath_1函数输出二叉树中最长路径, 需走一条从根结点开始到达二叉树最深层结点的路径, 从而调用该函数的次数为二叉树的深度 (当树中有n个结点, 即问题的规模为n时, 则该函数的平均调用次数为lg2n, 最坏情况下为单枝二叉树形态, 则树的深度为n) 次。另外, 在该函数体中包括两条调用PostTreeDepth函数的语句, 执行过程为:SearchLongestPath_1函数参数为根结点A时, 分别将A的左孩子结点B和右孩子结点C作为两次调用PostTreeDepth函数的参数, 其递归调用总次数为除去结点A后的其余结点及空指针的总个数 (2n) ;当SearchLongestPath_1函数的参数为结点B时, 两次调用PostTreeDepth函数的参数分别分B的左孩子和右孩子, 此时该函数的递归调用次数为B结点的子树中结点的总个数和空指针个数之和 (平均约2n/2-1, 最坏情况下为2n-1次) ;这样依次类推, 随着问题的规模n逐渐增大, 算法的时间复杂度接近n (2n+1) 。
2.4.2 非递归模拟算法时间复杂度分析
BtreeDepth函数体中包含一个while循环, 其基本语句为if-else语句, 该语句的语句频度函数即循环体的执行次数, 因而算法的时间复杂度为树的深度 (平均情况下为lg2n, 最坏情况下为单枝二叉树形态, 则树的深度为n) 。
SearchLongestPath_2函数体中同样包含一个while循环, 其循环体的执行次数也为树的深度, 即平均情况下为lg2n, 最坏情况下为n。循环体内两次调用BtreeDepth函数, 从而整个算法的平均时间复杂度接近 (lg2n) 2, 最坏时间复杂度接近n2。
可见, 搜索二叉树中最长路径的算法中, 当二叉树形态接近完全二叉树时, 非递归算法的时间效率较高;在接近单枝形态的二叉树中, 非递归算法的时间效率仍略高于递归的算法。
3 结论
递归算法的时间效率较差, 因此对于问题的解决通常可用递归算法的思路来分析, 而用非递归算法具体实现[2]。
递归算法的非递归模拟是数据结构教学中的一个难点。本文通过对搜索二叉树中最长路径的算法进行分析, 介绍了对该递归算法进行递归消解的具体方法, 给出了分析过程和C语言算法描述 (文中列出的所有算法的C语言程序均已通过上机测试) , 并对递归消解前后的算法进行了效率对比, 对数据结构相关内容的教学起到了一定的指导作用。
参考文献
[1]朱站立, 刘天时.数据结构—使用C语言 (第2版) .西安:西安交通大学出版社, 2000:121—159
[2]王敏.递归算法的时间效率分析.渭南师范学院学报, 2003;18 (5) :61—62
[3]严蔚敏, 吴伟民.数据结构.北京:清华大学出版社, 2000:54—56
[4]耿国华.数据结构——C语言描述.西安:西安电子科技大学出版社, 2006;65—69, 123—128
[5]徐孝凯.数据结构简明教程.北京:清华大学出版社, 1995:97
二叉树的遍历 篇2
关键词：二叉树,遍历二叉树,搜索路径
遍历是二叉树最重要的运算之一,是对二叉树进行其他运算的基础。
1 遍历方案
遍历(Traverse)是指沿着某条搜索路线,依次对树中每个节点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
从二叉树的递归定义可知,一个非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
1)访问根结点(D);
2)遍历该结点的左子树(L);
3)遍历该结点的右子树(R)
以上三种操作有六种执行次序:DLR、LDR、LRD、DRL、RDL、RLD。
2 遍历的命名
根据访问根结点操作发生位置命名:
DLR:先序遍历(Preorder Traverse,亦称前序遍历)访问根结点的操作发生在其左右子树之前。
LDR:中序遍历(Inorder Traverse)访问根结点的操作发生在其遍历左右子树之中(间)。
LRD:后序遍历(Postorder Traverse)访问根结点的操作发生在遍历其左右子树之后。
注意:由于访问是根据根结点D操作位置命名,所以DLR、LDR、LRD分别又称为先根遍历、中根遍历、后根遍历。
3 遍历方法
第一,如何通过给定的二叉树,写出三种遍历序列;
第二,如何通过给定的其中两中遍历序列,求出另一种序列以及画出对应的二叉树图。
下面通过具体的例题给出具体的解答:
如:假设一棵二叉树的先序序列为124536,中序序列为425136。请写出该二叉树的后序序列及其画出对应二叉树
解答过程如下:
1)由先序序列124536,可以得出根结点为1;
2)结合1),由中序序列425136,可以得出425为左子树(中序遍历),36为右子树(中序遍历);
3)结合2),根据先序序列124536,可以得出左子树245采取先序遍历根结点为2(即根结点1的左子树为2);右子树36采取先序遍历根结点为3(即根结点1的右子树为3);再由2),根据425采取中序遍历得出2的左子树为4,右子树为5;再由2,根据36采取中序遍历得出3的右子树为6
所以可以得出:1为根结点,2、3为1的左右子树,4、5为2的左右子树,6为3的右子树;
对应的二叉树如下:
4)根据二叉树图,结合后序遍历的规则LR1,L为根据L也是采取后序遍历为452,R也是采取后序遍历63,代入LR1,得出后序序列为452631。
同理,根据给出的二叉树,采取相同的方法,可以得出先序序列为124536,中序序列为425136。
参考文献
[1]安训国.数据结构[M].4版.大连:大连理工大学出版社,2009:96-101.
二叉树电子家谱设计 篇3
1 电子家谱系统简介
1.1 系统复杂性
李士勇认为复杂性是指系统在演化过程中和环境交互作用, 呈现出的复杂的动态行为特性和突出的整体特性。除此之外, 人们一般认为复杂系统是由众多存在复杂相互作用的组分 (或子系统) 组成的。家谱系统涉及众多子系统, 形成了规模庞大的多层次结构, 因此家谱系统具有多方面的复杂性。
1.2 系统结构
家谱是家族成员间相互联系组成一种体系结构。同家谱数据中由后代节点和父代节点分别组成家谱树的特点对应, 家谱系统通常采用树形结构。
2 二叉树家谱系统设计
2.1 家谱的体系结构
二叉树能够很好的反映家谱中成员之间的关系。本文系统中使用父子——兄弟结构, 即左子树第一个节点为父节点的儿子 (或兄弟) , 同理右子树第一节点表示父节点的兄弟 (或儿子) 。并且采用三叉链表的方式存储二叉树, 不仅便于对字节点进行查找, 还可以回溯查询关联节点确定成员间关系。
2.2 家谱成员及功能设计
2.2.1 数据单元设计
选定家族成员作为数据基本单元, 并在程序中定义为结构体Bi TNode。因为在一个家族中, 家谱中每个家族成员是最基本的组成部分。Bi TNode结构如下:
typedef struct Bi TNode{
标记、姓名、生日、住址、婚否、建在否、性别、妻子 (如已婚) 、死亡日期 (如已死亡) ;
struct Bi TNode*lc, *rc, *father;
}Bi TNode, *Bi Tree;
2.2.2 功能设计
系统设计了多种实用功能, 主要功能有:
3 设计实现的注意要点
建立树时, 由于新申请结点的孩子指针、兄弟指针等均未赋空值;但在函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用函数时出现系统保护异常 (使用了不安全的指针) 。因此在系统初始化时, 需要对以上几种属性赋予无影响初始值。
删除结点时, 只考虑到删除本身结点, 而其孩子结点的情况未考虑, 故在删除某些结点时会出现“断链”现象。故在删除某一结点时, 首先要判断此结点是否有孩子及兄弟, 然后进行相应操作。
4 结语
电子家谱系统是一种重要工具, 它使家谱得以充分保护和使用。笔者的二叉树电子家谱系统设计提高了家谱使用的实用性和易用性, 为家谱系统的电子信息化打下了一定基础。家谱电子信息化是一个庞大的系统工程, 今后我们将研究家谱便易搜索算法以及家谱成员流动模式。
参考文献
[1]王鹤鸣.中国家谱通论[M].上海:上海古籍出版社, 2010:4.
[2]司马贺.人工科学:复杂性面面观[M].上海:上海科技教育出版社, 2004:78-79.
[3]李士勇.非线性科学与复杂性科学[M].哈尔滨:哈尔滨工业大学出版社, 2006:23.
题解二叉树的构造 篇4
关键词：数据结构,二叉树遍历,二叉排序树
学习过数据结构的读者们都知道, 在二叉树的遍历章节中, 有一种比较典型的题型是: 给出一棵二叉树的先序遍历序列及中序遍历序列, 据此构造出这棵二叉树。 这个问题一般都是根据二叉树的前序遍历和中序遍历定义及二叉树的性质求解的。 笔者在学习过程中发现另一种解决方案, 即利用二叉排序树的定义来求解。 下面笔者将两种方案一一介绍如下。
一、利用二叉树遍历定义求解
一般书中的常见解法为:由二叉树的遍历定义得知, 二叉树的前序遍历是先访问二叉树的根结点, 然后遍历左子树, 最后再遍历右子树, 也就是根-左-右的顺序。 这样, 在遍历结点的前序序列中, 第一个结点一定是根;而用中序遍历时, 是先遍历左子树, 再访问根结点, 最后遍历右子树, 是左-根-右的顺序, 由此知道, 根结点将中序遍历序列分割成两个部分:在根结点前是左子树的中序遍历序列, 在根结点之后则是右子树的中序遍历序列。 反之, 根据左子树的中序遍历序列中结点的个数, 又可将前序序列除根以外分成左子树的前序序列和右子树的前序序列两部分。 依次类推, 我们就得到了整棵二叉树。
如下例:
例1: 已知二叉树结点的前序序列为:ABCDEFG, 中序序列为:CBDAFEG, 试绘出这棵二叉树。
解1: 首先由前序序列得知二叉树的根为A, 则由中序遍历序列得出其左子树的中序遍历序列为 (CBD) , 右子树的中序遍历序列为 (FEG) 。 反过来, 又由前序序列得知其左子树的前序序列必为 (BCD) , 右子树的前序序列为 (EFG) 。 由左子树的前序序列 (BCD) 得出左子树的根结点为B, 又由左子树的中序序列 (CBD) 得出以B为根的左子树的左边叶子结点为C, 右边叶子结点为D。 同理, 可构造得出右子树。
构造过程图示如下:
二、利用二叉排序树的定义求解问题
二叉排序树是一种特殊的二叉树, 它的每一个结点数据中都有一个关键值, 并且对于每个结点, 如果其左子树非空, 则左子树的所有结点的关键值都小于该结点的关键值, 如果其右子树非空, 则右子树的所有结点的关键值都大于该结点的关键值。 根据其定义可知, 对二叉排序树进行中序遍历, 将得到一个按结点关键值递增有序的线性序列。若从一棵空树出发, 构造一棵二叉排序树, 则每次插入的新结点都是二叉排序树上新的叶子结点, 我们可以假设为:从一棵空树出发, 构造一棵二叉排序树, 每次插入的新结点序列即为这棵二叉排序树的前序序列。由此我们得出文中问题的第二种解决方案:
1.将给出的中序序列中每个结点按升序依次赋一关键值;
2. 根据第一步中所赋之值得到前序序列的关键值序列;
3. 以前序序列所得到的关键字序列构造一棵二叉排序树;
4. 将构造出的二叉排序中的关键字用原结点值换回。
下面我就以第二种解决方案来解上文中的例1。
解2:将题中中序序列 ( CBDAFEG) 中每个结点按升序依次赋一关键值, 如结点C对应关键值为1, 结点B对应关键值为2, 结点D对应的关键值为3, 结点A对应的关键值为4, 结点F对应关键值为5, 结点E对应关键值为6, 结点G对应关键值为7。
然后按前序序列 (ABCDEFG) 的关键字序列 (4, 2, 1, 3, 6, 5, 7) 构造一棵二叉排序树, 构造过程如下:
最后将所构造成的二叉排序树中的各关键值用原结点值换回, 所得出二叉树如下所示:
问题即得解。
比较这两种问题的解决方法, 各有优劣。用第一种方法, 不需掌握二叉排序树的相关知识, 但如果此二叉树结构较复杂, 结点较多时, 使用此种方案, 易造成思路混乱, 速度较慢的后果, 而使用第二种解法较简便快捷。
参考文献
[1]严尉敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.
[2]蔡子经, 施伯乐.数据结构教程[M].上海:复旦大学出版社, 1994.
[3]刘清, 王琼.数据结构[M].北京:电子工业出版社, 2001.
二叉树结构的文本模式显示 篇5
检查二叉树结果可以通过输出二叉树的遍历结果来进行,尤其是层序遍历[2];也可以在集成开发环境中通过监视(Watch)追踪左右子树,这不直观也非常繁琐。图形显示二叉树是比较直观和形象的[3],因此在教学中可以采用图形显示[4,5],比如图1;但是它的缺点也很明显,要求学生掌握一定的图形编程,而不少学生在学习数据结构的时候图形编程基础比较弱,因此教与学往往是在命令行的方式下进行输出,即通过printf或cout进行输出(C/C++语言),所以采用图形输出进行数据结构教学有一定的局限性。
叶品菊等开发了在文本方式下显示二叉树的方法[2],该方法用层序进行输出,每一层输出在一行中,但该方法父结点与子结点之间没有任何东西相连(如图2),因而输出的图形不像一颗树,而是结点的有规律的排列,显示的直观性略差。任燕在其编著的教材《数据结构C++语言描述》[6]中,二叉树的示例图是屏幕截图的,从图中可以看出它利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,显示效果非常直观与形象,与图形模式下的显示方式基本相同,只是链式存储二叉树需要转换成顺序存储二叉树,“以便使链式存储二叉树能以树状形式显示”[6]。该文给出了一种文本模式的二叉树结构显示方法,该方法利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,使用队列对链式存储二叉树进行层序输出,该方法进行较小的改动可以应用于顺序存储二叉树的显示,加入特殊字符’|’经适当修改也可顺利地显示3阶B_树。由于该方法直观形象且是文本模式,因而可以作为数据结构教与学的有效手段之一。
1 显示方法
文本模式下的二叉树显示主要的是计算结点的输出位置,输出位置是由空格的多少来决定的,父结点与子结点之间的连接由三种特殊字符’_’、’/’和’’构成。倒数第一层和倒数第二层之间只需’/’和’’就可连接,左子树由’/’连接,右子树由’’连接。其它层数之间的结点连接由两行构成,第一行连接线由一个或多个’_’与’/’或’’构成,左子树的连接线形如“_____/”,右子树的连接线形如“_____”;第二行的连接只需’/’和’’,左子树是’/’,右子树是’’。其它非连接线位置由空格填充。为了让斜线(/或)指向结点位置,结点不在斜线(/或)的正下方(文献[6]是在正下方),而是偏一格,这样底层结点相邻3个空格,这样的显示效果比文献[6]中的显示效果更为自然和美观。输出的具体编排见图4。
为了计算空格的个数,需要知道二叉树的显示宽度。由于底层结点相隔3个空格,因此二叉树的显示宽度为满二叉树的底层结点数乘4,高度为5的二叉树显示宽度是64个字符长度,高度为6的二叉树显示宽度是128个字符长度。而在文本模式下,由于文本模式每行80个字符(缺省属性)的限制,该文的显示方法只能显示高度不超过5的二叉树。如果要显示高度为6的二叉树,有两种方法,一是修改文本模式每行显示宽度的属性,只要每行可显示超过128个字符即可;二是显示时采用紧凑格式,结点在斜线的正下方[6],这样底层相邻结点之间只有一个空格,高度为6的二叉树显示宽度为64,显示效果见图5,与图3相比美观性略差。文献[2]采用分页的方式来显示高度超过6的二叉树。考虑到该文的方法主要用于教与学,高度为5的满二叉树有31个结点,对于教学来说高度与结点数都足够,因此该文方法不需其它的改动完全满足正常的教学要求。
空格的具体个数依赖于结点所处的层数,计算时分数据域行、第一行连接符和第二行连接符,倒数第一层和倒数第二层之间只有第一行连接符。具体计算公式如下:
数据域:(2n-2个□)a(2n+1个□)(n为树高,□代表空格,a为数据)
第一行连接符:(2n-1个□)(2n-1-3个_)/□(2n-1-3个_)(2n-1+3个□)
第二行连接符:(2n-1-1个□)/(2n-3个□)(2n-1+2个□)
计算第一行连接符时,n=2将导致2n-1-3=-1,因此前面的空格需要减少一个,即2n-1个空格变为2n-1-1个空格。第二行连接符计算时,不会出现这种问题,因为n=2时没有第二行连接符。
2 程序实施
根据以上方法采用C++进行编程,二叉树的类定义如下:
二叉树的输出是从根结点开始,一层一层地输出。每一层分3行输出,第一行输出结点数据,简单起见结点数据类型为字符型;第二行和第三行为连接符,第一行连接符包括三种字符’_’、’/’和’’,第二行只包括’/’和’’两种字符。如果不用字符’_’而用字符’~’也可以,此时第一行连接符包括’/’和’’,第二行包括’~’、’/’和’’三种字符。倒数第一层没有连接符,倒数第二层没有第二行连接符。每一行输出时一个结点一个结点地输出,空结点也需输出,只是结点数据和连接符全部用空格替代。
由于整体输出顺序是层序,因此用结点指针型的队列来处理层序输出;每一层的结点需重复3次进行输出处理,每个结点处理完后需要放回到队列以便重复提取。每一层的3行输出结束后队列需要更新,即下一行的结点进入队列。由于空结点也需处理,队列一直不空,为了充分利用队列,用一个临时结点来表示一层结点的处理结束,否则需要计数处理。加了注释的代码如下:
由于空结点也需要处理,因此代码中有大量的分支语句;为了压缩代码长度,程序编制时大量使用了三目运算符?:。即使这样程序仍有70余行,如果希望进一步压缩代码,三行输出的循环控制压缩到一个循环,此时第一行和第二行的连接符需要存储在两串字符串中,循环结束再输出。这样处理后代码压缩到50余行,压缩量不大且可读性略有下降,不建议这样处理。
3 实例应用
二叉树是数据结构中的基础数据类型,因此应用的地方较多,该文举几个简单的例子。二排序叉树是有利于搜索的数据类型,采用该文方法把搜索的结果用特定字符’*’标识出来如图6。哈夫曼树是一种最优二叉树,带权的初始结点都在叶子上,构造过程中新建的结点都是分支结点;哈夫曼树可以采用顺序存储[6],该文方法略作修改即可应用于顺序存储,用特殊字符’@’标识分支结点显示的哈夫曼树如图7。平衡二叉树是一种优化后的二叉排序树,它的左右子树的高度不超过1,每个结点有一个平衡因子表示左右子树的平衡情况,可以用更为直观的符号表示平衡因子,即’>’代表1、’=’代表0和’<’代表-1,显示时把数据域后面的空格减少一个,用于输出平衡因子的代表符号,显示结果如图8。B_树是一种多路平衡查找树,可用于外部文件的动态查找,B_树的插入与删除算法比较复杂,非常适合学生的编程技能训练,在调试过程中如何快速有效地检查结果比较麻烦,采用该文的方法经适当地修改可以方便地显示3阶B_树。为了显示3阶B_树,增加一个符号’|’指向中间的子树,最重要的修改是显示起始位置的计算,另外用字符’~’替代了字符’_’,此时第一行连接符包括’/’、’|’和’’,第二行包括’~’、’/’、’|’和’’四种字符,这样显示的效果也非常好,如图9。
4 结论
二叉树结构的文本模式显示方法使用了’_’、’/’和’’三种字符来显示二叉树的结构,由于不涉及图形操作,该方法有很强的可移植性,不论TC环境或者VS环境,该文提供的代码都可直接使用。该文的方法也可方便地改为独立的函数,也方便其它的语言实现。该方法方便了树型数据结构程序的调试,不仅可以应用于各种二叉树,也可应用于三叉树,比如3阶B_树。由于直观地显示了二叉树的结构,因而可以提高教与学的效率。同时,算法也使用了队列,对学生巩固已学过的数据结构知识非常有帮助。
参考文献
[1]中国计算机科学与技术学科教程2002研究组.中国计算机科学与技术学科教程2002[M].北京:清华大学出版社,2002.
[2]叶品菊,吴斌,胡远望,等.直观显示二叉树结构的算法[J].江南大学学报:自然科学版,2008,7(1):60-63.
[3]刘福君,李华,王玉森,等.基于二叉树的故障树画树算法研究[J].计算机技术与发展,2006,16(7):117-118.
[4]刘惠敏,董毅.动态模拟二叉树的建立[J].黄冈职业技术学院学报,2004,6(1):75-76.
[5]白雪峰,李沛.二叉排序树的建立及对其中序遍历的动态模拟[J].电脑知识与技术,2005,12(8):84-86.
C语言递归生成二叉树探讨 篇6
叉树是一种基本的非线性数据结构, 二叉链表是其常用的存储形式。用二叉链表实现生成二叉树的算法比较多, 其中递归生成及递归遍历二叉树属于二叉树的基本操作。目前无论在教学或实用使用中, 大都采用C、C++或C#编程实现, 其中用面向过程基本C语言编程属于重要的基本实现方法。该文在基于基本C语言环境下对实现生成二叉树及遍历进行一些探讨。
该文二叉链表数据结构用C语言表示为:
2.二叉树递归生成
可以利用二叉树基本性质, 即从根结点开始, 不断给当前叶子结点添加左、右新的子结点, 生成整棵完整的二叉树。这里, 以前序递归方法为例来介绍。需要注意的是输入时按先序遍历次序输入二叉树中结点的字符值, 同时要把左右子树为空的结点也要表示出来, 该文用`#`表示空树。
下面给出几种C语言实现方案:
使用的宏定义:
方法2:
方法3:
对上面几种方法, 若有下面一颗二叉树 (图1) , 从键盘输入的字符为:abc##de#g##f###, 则都可得到正确的二叉树。
一种常见的错误方法:
错误的原因:形参不能把执行结果带出函数体外, 因此创建不了二叉树。如果是C++语言, 可以把函数首都定义为:void Create (BTree&a) , 可以得到正确的结果。但是, 基本C语言形参不支持地址 (&) 引用。这一点, 在编程时应格外注意。
3.二叉树递归遍历
遍历时从根结点开始, 依先访问根节点, 再访左结点和右结点的顺序递归往下访问所有的结点。对上面给定的二叉树, 前序遍历的顺序如图2所示。
有两种递归实现遍历的方法, 同样以前序遍历为例:
方法1:
方法2:
main主程序调用语句为:
其中, my＿tree为先前生成的二叉树。
说明:方法1程序较简单, 而方法2更通用一些。对于上面实验数据, 遍历输出的序列为:abcdegf。
4.结语
从上面分析可知, 用C语言实现生成二叉树时, 生成函数是否设置形参, 以及是否设置函数的返回值, 对执行的结果都有很重要的影响。遍历时, 也给出了两种递归实现方法。对于中序、后序生成及遍历, 应该调整根结点相对应左、右结点的顺序即可。在编程时应仔细考虑提到的问题, 注意细节, 避免出错。
参考文献
[1]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社, 2002
[2]盛魁.二叉树的遍历探究与应用[J].电脑知识与技术, 2008, 3 (5) :1014-1015
对广义平衡二叉树的检索时间分析 篇7
平衡二叉树之所以能保证检索的高速和稳定，是因为其平衡的特性，但是这一特性也额外的增加了增删节点时的操作开销，即维持平衡的开销。维持平衡一般采用旋转算法，其时间复杂度也是O(log n)。但是旋转操作并不是每次都需要的，比如当两次删除操作导致某子树的左右子树深度各减少1时，不会发生失衡，也无需进行旋转操作;由此可断言，如果将包含n个节点的AVL Tree的所有形态视为一个集合，假定对其中任意节点的操作频率以及操作方式(增加或删除)是一样的，那么这所有操作中引起失衡的概率是一个常数，而这一常数影响着应用系统的整体性能。
Caxton C.Foster提出的对AVL Tree的一种推广结构，他允许BST的平衡因子被放大到一个较大的正整数范围，降低由于结构变更导致失衡的概率，从而达到提升整体性能的目的。P.L.Karlton与S.H.Fuller等人也在这方面做了一定的研究。与他们主要依赖实验的研究方式不同，本文采用论证的方式分析了这种结构的在检索时的性质。
1 基本概念
高度平衡二叉树(Height balanced tree)的定义由Foster提出，我们描述如下。
定义1：给定整数N，则二叉搜索树HB(N)是容差为N的高度平衡二叉树，当且仅当满足以下条件：
1)T(N)的左子树和右子树的深度差(平衡因子，imbalances)的绝对值|Dleft-Dright|≤N。
2)任意子树均是容差为N的次平衡二叉树。
由定义不难看出，如果把其中的N替换成1，就成了AVL Tree的定义。事实上，根据这一定义有如下推论：
推论1:HB(0)是满树。显然，所有子树的左右子树完全一致，必然是满树，这是BST最严格的形式，其最坏检索时间就是log n。
推论2:HB(1)是AVL Tree。
推论3：如果一棵二叉搜索树是HB(m)，且有m
从定义我们可以可得，N越大时，HB(N)的最坏检索时间越大，对HB(N)的检索费时也越不稳定，但是失衡的概率会越小。在一定的容量(包含一定节点数)以及理想的状态(对每个节点的访问频率相同)下，平均检索时间和平均重构时间均为关于N的函数，分别记为S(N)和R(N)，失衡概率也是关于N的函数记为P(N)，显然S是增函数，P是减函数，R尚不确定。我们再假定应用程序中，提交的检索请求占比率p,相应的提交变更请求则占1-p;如果变更请求没有造成失衡，那么它的费时可以忽略不计。综合这些考虑，我们可以对该应用程序的平均运行时间做出定义：t(N)=p*S(N)+(1-p)*P(N)R(N)，那么t(N)的极值在t’(N)=0时达到，这就为设计者提供了一个方法，可以使得其编写的应用程序运行在最优状态。
这里我们仅对HB(N)的检索开销进行分析。
2 检索时间分析
很显然，原有的对于AVL Tree的存储、检索、增删节点的算法同样可以应用到广义平衡二叉树中，只需要修改一下对失衡的判定，将|Dleft-Dright|>1改成|Dleft-Dright|>N即可。因此，这些算法的空间开销并没有发生改变，这里主要讨论其时间开销。
HB(N)的检索时间取决于HB(N)的深度，其最坏检索时间实际上就是HB(N)的深度，而平均检索时间则是小于最坏检索时间的一个值，因此，我们针对其深度进行分析。
命题1：对于深度为D的HB(N)，其D/(N+1)层以上部分为满树。
证明：
设从上至下，x是第一个不健全的节点(没有左子树或右子树)，P(x)是求父节点的函数，D(x)是求深度的函数。
由于x缺少一棵子树，所以其另一颗子树的深度不超过N，否则x不是HB(N)，故D(x)≤N+1。而x是P(x)的子树之一，故另一棵子树深度不超过D(x)+N，所以D(P(x))≤2(N+1)。同理P(x)是P2(x)的子树，故P2(x)的另一子树深度不超过2(N+1)+N+1=3(N+1)……
重复以上操作可得：D(Pl(x))≤(l+1)(N+1)
设Pl(x)是树的根节点，故D=D(Pl(x))≤(l+1)(N+1)，故l≥[D/(N+1)]-1。
而Pl(x)是根，x=P0(x)是第一个不健全节点，所以从根开始，完整的层数为l+1层，故D/(N+1)层以上部分为满树。
命题2：深度为D的HB(N)至少包含αD-1个节点，其中α是αN+1-αN-1在(1,2]之间的根。
首先来看α的存在性，我们定义函数f(α)=αN+1-αN-1，它在(0,∞]上是连续的，且有f(1)=-1<0,f(2)=2N(2-1)-1，当N≥0时，f(2)≥0。根据介值定理，f(α)在(1,2]上必然有解，α是存在的。
为了简便，下文中将用αN表示αN+1-αN-1在(1,2]之间的根。
为了证明命题2，这里先证明两个引理。
引理1：αNN≤N+1
证明：
假设αNN>N+1，根据αN定义有1=αNN(αN-1)>(N+1)(αN-1)，所以，αN<1+1/(N+1),于是αNN<[1+(1/(N+1))]N，联合假设得到(1)式N+1<αNN<[1+(1/(N+1))]N。
在N≥0时，[1+(1/(N+1))]N是趋向于自然对数底数e的增函数，e≈2.718<3，故当N≥2时(1)式不能成立。而N=0或N=1时，均可验证得到矛盾。
因此，假设不能成立，有αNN≤N+1。
引理2：自然数D≤N+1时，αND-1≤D。
证明：
将D视作未知数，N视为常数，由此αN也是常数。
令f(D)=αND，有f''(D)=αND(lnαN)2>0，所以f(D)是递增的凹函数。
令g(D)=D+1，是线性函数。
当D=1时，有f(D)=αN≤2=D+1=g(D)。
当D=N+1，有f(D)=αNN+1，根据αN定义，得到f(D)=αNN+1，又根据引理1，可f(D)≤N+2=g(D)。
根据凹函数的性质可以推断，当D≤N+1时均有f(D)≤g(D)成立，即αND-1≤(D)。
下面证明命题2:
使用归纳法，令C(t)表示二叉树t的节点个数，Left(t)和Right(t)分别表示t的左右子树。
当D≤N+1时，容差为N的平衡二叉树t的极端形式就是链表，所以C(t)≥D，根据引理2可得C(t)≥αNN-1，命题2成立。
设当D∈[1,p]且p≥N+1时命题2成立，则D=p+1时，t可以看作两棵T(N)加上一个根节点组成的二叉树。这两棵T(N)中一棵深度为p，另一棵的深度在[p-N,p]上，否则t将不满足容差为N的平衡条件，并且很显然，这两棵子树的深度都在[1,p]区间上了。根据假设，t的节点个数可如下计算：
根据αN定义，C(t)=αNp-NαNN+1-1=αNp+1-1，即D=p+1时命题2也成立。
综上所述，在D为自然数的情况下，均有命题2成立。
推论4：包含n个节点的T(N)深度不超过log(n+1)/logαN。
由此可见，T(N)和满树在最坏检索时间相差倍数不超过logα0/logαN，这个倍数的取值与N的关系从表1和图1、图2中可以清晰反映。
3 结论
本文用理论方法考查了广义平衡二叉树的深度范围，得到了取值范围的上限表达式，并且这个上限表达式是便于计算的。从而我们能够迅速的得到，当我们设定容差N后，其检索时间的最大范围，为应用程序设计者提供了很好的理论依据。
但是，本文证明的结果所能指示的仅仅是一个上界，而不是上确界，也就是说实际的最坏检索时间比这个结果还要小，而平均检索时间则更加小。这是本文结果的缺陷所在，同时又证明了广义平衡二叉树确实有比AVL Tree更好的应用价值。
参考文献
[1]Adel'son-Vel'skii G M,Landis E M.An algorithm for the organization of information[J].Doklady Akad.Nauk.USSR 146,2,1962.
[2]Foster C C.A generalization of AVL trees[J].Communications of the ACM,1973,16(8).
[3]Karlton P L,Fuller S H,Scroggs R E,et al.Performance of Height-Balanced Trees[J].Communications of the ACM,1976,19(1).
[4]唐自立.一种新的删除HB(k)树的结点的算法[J].计算机工程与应用.2007,43(5):45-48.
[5]Andersson A.General Balanced Trees[J].Journal of Algorithms,1999(30):1-18.
[6]Pfaff B.Performance Analysis of BSTs in System Software[D].ACM SIGMETRICS Perfor-mance Evaluation Review,2004.
[7]Baer J L,Schwab B.A Comparison of Tree-Balancing Algorithms[J].Communications of the ACM,1977,20(5).