非递归二叉树初始化

非递归二叉树初始化（精选5篇）

非递归二叉树初始化 篇1

树形结构是一种重要的数据结构,而二叉树又是一种最常用的树形结构。在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理,即二叉树的周游,也称为遍历。所谓周游二叉树,就是按照某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。由于二叉树是一种非线性结构,二叉树由3个基本单元组成:根结点、左子树和右子树。因此,若能依次周游这3部分,便周游了整个二叉树。假如以L、D、R分别表示周游左子树、访问根结点和周游右子树,则按照先左后右的顺序,深度优先周游二叉树的方法通常有3种:前序法(DLR)、中序法(LDR)和后序法(LRD)。

对于用顺序法表示的二叉树,各结点在数组中的编号很有规律,其周游较容易进行,但对于用链式存储结构表示的二叉树,进行周游就复杂一些,仅讨论二叉链表存储的二叉树的周游算法。首先讨论深度优先周游二叉树的递归算法,然后研究深度优先周游二叉树的非递归算法。

1 深度优先周游二叉树的递归算法

前序法(DLR)的递归定义是:若二叉树为空,则空操作;否则:访问根结点;前序周游左子树;前序周游右子树。

中序法(LDR)的递归定义是:若二叉树为空,则空操作;否则:中序周游左子树;访问根结点;中序周游右子树。

后序法(LRD)的递归定义是:若二叉树为空,则空操作;否则:后序周游左子树;后序周游右子树;访问根结点。

深度优先周游二叉树的次序是递归定义的,因此其递归算法是很容易实现的。若二叉树的二叉链表存储结构定义为:

则3种深度优先周游二叉树的递归算法分别为:

从上述深度优先周游二叉树的定义可知,3种周游算法的不同处仅在于访问根结点和周游左、右子树的先后关系。深度优先周游二叉树的递归算法的实现,在系统运行时是借助栈来完成的。以图1所示的二叉树为例,分析栈的变化过程。前序周游二叉树与中序周游二叉树时,栈的变化相同,而后序周游二叉树则稍微复杂一些。如表1、表2和表3所示。

2 二叉树的非递归周游算法

根据上述二叉树周游时的栈的变化情况,可以看出:二叉树的前序周游和中序周游时栈的变化情况完全相同,不同的是前序周游时,进栈时访问元素;而中序周游时,出栈时访问元素。由此设计二叉树的DLR和LDR的非递归周游算法如下:

使用栈进行前序周游时,遇到一个结点,就访问该结点,并把该结点推入栈中,然后下降去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。

使用栈进行中序周游时,遇到一个结点,就把它推入栈中,并去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点并访问之,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。

使用栈进行后序周游二叉树时,遇到一个结点,把它推入栈中,去周游它的左子树。周游遍它的左子树后,还不能马上访问处于栈顶的结点,而是要再按照它的右孩子指针指示的地址去周游该结点的右子树。周游遍右子树后才能从栈顶托出该结点并访问之。为此,需要设一个标志,以标识右子树已被周游。算法中设置了一个指针标志pre,表示刚刚访问的结点。如果当前结点的右孩子为pre,就说明右子树已被访问,接下来是访问当前结点了。

3 深度优先周游二叉树的算法性能分析

上述深度优先周游二叉树的递归算法与非递归算法的时间复杂度均为O(n),空间复杂度在理想情况下为O(log 2n),如二叉树退化为单支树时,则空间复杂度为O(n)。

由于递归算法结构清晰,程序易读,而且它的正确性容易得到证明,因此,利用允许递归调用的语言进行程序设计时,给用户编制程序和调试程序带来很大的方便。因为对这样的一类递归问题编程时,不需要程序员而由系统来管理递归工作栈。而非递归算法更方便读者理解工作栈的变化情况,但需要程序员决定栈所占据的存储空间大小,为保证二叉树周游不至于因为栈溢出而进行不下去,就需要给栈分配足够的存储空间。

摘要：给出了深度优先周游二叉树的前序、中序、后序的3种递归算法,在分析了周游二叉树的递归算法中的工作栈的执行过程的基础上,设计了先序、中序、后序周游二叉树的非递归算法,对深度优先周游二叉树算法的性能进行了分析。

关键词：二叉树,周游,递归,非递归,栈

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社,2010.

[2]许卓群,杨冬青,等.数据结构与算法.高等教育出版社,2006.

非递归二叉树初始化 篇2

递归是软件设计中一种重要的方法和技术。满足递归要素的问题具有三个特征:⑴原问题具有某种可借用类同自身的子问题描述的性质;⑵子问题相对于原问题有进一步的简化;⑶某一有限步的子问题有直接解存在[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

二叉树操作的递归算法分析 篇3

二叉树是数据结构课程内容中的重点和难点,学好数据结构就必须要掌握二叉树的存储结构和基本操作的算法。二叉树最常用的存储结构是二叉链表,根据二叉链表的示意图,我们很容易理解二叉树的这种存储形式。因此,掌握二叉树的关键就是要理解二叉树基本操作的算法。本文将分析二叉树操作的递归求解方法,以求和数据结构爱好者共同学习和研究。

2 递归

递归是一种非常有用的算法设计工具。一个函数、过程如果在其定义或说明内部直接地或间接地出现有其本身的引用,这种用自己定义自己的方法称之为递归[1]。

递归方法实际上是将一个原问题转化为和原问题相同的子问题,只不过子问题的规模比原问题的规模要小。这种转换多次进行,直到满足某个约束条件为止。用递归方法求解问题关键就是要确定两方面内容:(1)子问题(2)递归结束条件。

例如:求n!

因此,可将原问题“求n!”转换为子问题“求(n-1)!”,原问题和子问题为同样的问题,都是求某数的阶乘,但子问题数字小。随着不断转换,子问题数字越来越小,当求1!时,可直接给出值1。所以,递归结束条件就是n=1。

3 二叉树操作的递归求解方法

二叉树的特点是每个结点至多只有两棵子树(左子树和右子树),且左右子树也是二叉树。因此,二叉树或者为空,或者可分为三部分:根结点、左子树、右子树。由于二叉树中的左子树和右子树也是二叉树,因此,二叉树的组成具有递归的特点,那么,二叉树的许多操作可考虑用递归方法来描述。下面将讨论几个常见二叉树操作的递归算法。

3.1 遍历二叉树

遍历二叉树是指按某条搜索路径巡访二叉树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次[2]。常见的二叉树遍历方法有三种:先序遍历、中序遍历、后序遍历,下面以先序遍历为例,分析其递归算法。

先序遍历二叉树的思想是:若二叉树为空,则没有任何结点可访问,因此空操作;当二叉树不为空时,先序遍历二叉树就是要:访问根结点、先序遍历左子树、先序遍历右子树。采用递归方法分析:1)原问题为先序遍历二叉树。2)原问题可分为三步:访问根结点、先序遍历左子树和先序遍历右子树。访问根结点直接对应访问语句,例如输出语句。先序遍历左子树和先序遍历右子树这两个问题都属于先序遍历二叉树的问题,与原问题一样,只不过左子树和右子树比原二叉树规模要小。因此,子问题为先序遍历左子树和先序遍历右子树。3)递归结束条件就是二叉树为空。

确定递归算法的子问题和递归结束条件后,就可写出先序遍历的递归算法:

3.2 建立二叉树的二叉链表

建立二叉树的二叉链表存储结构是二叉树的必备操作,因为在程序中,只有创建了二叉树的二叉链表存储结构,才可以进行二叉树的其他操作。显然,二叉树中的每个结点对应二叉链表中的一个结点,因此,创建二叉链表,就是要为二叉树中的每个结点建立一个结点存储结构。可以按照某种遍历顺序依次为各个结点建立存储结构。若按照中序遍历顺序或后序遍历顺序建立,则在建立二叉链表过程中,已建立的结点是分散的、不能连接成一个链表,这就不易掌控所有已建立的结点。如果按先序遍历顺序建立,则已建立的结点都可链接在根指针所指的二叉链表中。因此,可按先序遍历的顺序为各个结点建立存储结构。

建立二叉树的二叉链表的算法思想是:若二叉树为空树,则根指针应设置为空;若二叉树非空,则为根结点建立存储结构,再建立左子树的二叉链表和右子树的二叉链表。采用递归方法分析:1)原问题为建立二叉树的二叉链表。2)子问题为建立左子树的二叉链表和建立右子树的二叉链表。3)递归结束条件是二叉树为空树。

根据用户输入的序列,建立二叉树的二叉链表的递归算法如下:

使用此算法建立二叉树的二叉链表,用户在输入结点序列时要注意:空子树也要输入,用空格代表空子树。例如图1所示二叉树,应首先标出空子树,见图2,然后对其先序遍历得到输入序列:AB__CD__E__。

3.3 求二叉树的深度

二叉树深度可按如下规则求取:当二叉树为空树,则深度为0;当二叉树只有一个结点,则深度为1;否则,二叉树的深度为左子树深度和右子树深度中的较大值,再加上1。采用递归方法分析:1)原问题为求二叉树的深度。2)子问题为:求左子树深度和求右子树深度。3)递归结束条件是二叉树为空或者二叉树只含有一个结点。根据上面分析,可得到如下递归算法:

3.4 返回结点e的左兄弟

采用递归方法分析:1)原问题为在一棵二叉树中找结点e的左兄弟。2)子问题可设定为在左子树中找结点e的左兄弟,和在右子树中找结点e的左兄弟。3)递归结束条件可有两种情况:a)若二叉树为空树,则结点e的左兄弟不存在;b)若根结点的右孩子为结点e,则结点e的左兄弟为根结点的左孩子。递归算法如下:

4 总结

二叉树是数据结构课程中的重要内容,掌握二叉树关键是掌握二叉树各种操作的算法。本文采用递归方法分析了二叉树的先序遍历、创建二叉链表、求深度、求结点e的左兄弟这四个操作的求解方法。对于二叉树的许多其他操作,也可以与此类似,采用递归方法求解。

摘要：二叉树是数据结构课程中的重点内容。由于二叉树本身具有递归的特点,因此二叉树的许多操作可采用递归方法求解。该文首先介绍了递归方法,然后采用递归方法分析二叉树的几个常见操作,并给出详细算法。

关键词：递归,二叉树,遍历,算法

参考文献

[1]李伟.浅析C语言递归算法[J].电脑知识与技术,2012(10).

C语言递归生成二叉树探讨 篇4

叉树是一种基本的非线性数据结构, 二叉链表是其常用的存储形式。用二叉链表实现生成二叉树的算法比较多, 其中递归生成及递归遍历二叉树属于二叉树的基本操作。目前无论在教学或实用使用中, 大都采用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

论复杂二叉树的初始化算法 篇5

1 二叉树的初始化

现在二叉树[1]的创建主要用两种方法, 第一种是递归的方式, 第二种就是非递归的方式。那他们是怎么实现的呢?首先说一下递归的方法。递归的话有很多的算法, 也有对它进行的改版, 不过万变不离其宗。先说下递归的思想, 我们先定义一个二叉树类型BTN和一个二叉树类型的指针BT, 二叉树里包括节点的值我们假设定义成char data, 还有左孩子和右孩子分别为struct BTN*zuo, *you。递归的思想就是先写一个方法, 方法必须有形参, 而且形参的类型必须是BT&bt, 这个形参有两个作用: (1) 初始化哪个二叉树, 这个形参就是初始化的二叉树, 所以要先定义一个二叉树指针, 在这里我们假设定义root是一个二叉树的指针。 (2) 供自己递归使用而且必须是引用或者指针, 因为这样二叉树出了这个函数仍然是能够在其他的方法里用的, 不会为空。否则, 走出这个函数就会和原来一样是空值, 即这个初始化和没初始化一样, 那我们的工作就白做了。所以这个形参应为引用或者指针。

接下来我们在方法里先分配空间, 然后用指针T指向这个节点。那么T就是根节点, T->data=输入的值, 即根节值。然后调用本函数, 在这里我们假设生成二叉树函数为void chushihua (BT&bt) , 那么输完根节点就应该输入左孩子, 即chushihua (T->zuo) 。因为左孩子也是一个节点, 所以可以再调用自己的函数, 生成右孩子根节点的方法类似, 也是调用本函数, 调用方法chushihua (T->you) 。

思想就是这样, 但是怎么输入呢?一般递归的输入有两种方法:

第一种方法就是定义一个字符变量, 在这里我们假设为char jd, 在创建二叉树的时候让用户输入一串字符, 当然这个字符是有顺序的, 我们假设顺序为二叉树先序。然后再把每个字符分给每个节点, 从而完成二叉树的初始化。这种方法的弊端就是当二叉树很庞大很复杂的时候, 二叉树的先序序列比较复杂, 这给用户的输入带来了很多的不便, 特别是对于没有编程基础的用户, 二叉树的初始化不好完成。再说我的方法, 我的方法和第一方法差不多, 就是每输入一个结点就赋一个值, 直到把所有的二叉树结点的值赋完, 那么这个二叉树就算是初始化成功。

接着再说一下非递归的二叉树的初始化。其实非递归的二叉树只不过名字上是非递归, 我认为其实还是递归的, 为什么这样说呢?因为递归的算法原理是用的栈的原理, 先进后出, 同样的非递归的算法, 虽然没有递归调用它自己, 但是必须借助栈或队列, 才能实现非递归的算法, 所以我认为非递归是递归一种变形。如何通过非递归来实现二叉树的初始化呢?需要借助栈或者队列, 当然, 非递归有点复杂, 不像递归那样简单, 也不像递归那样容易理解。非递归的算法也有很多种, 同递归一样, 很多的非递归算法也要求用户输入的是先序或者广义表形式等, 这样当二叉树很庞大很复杂的时候, 像递归一样, 会给用户带来很多的不便, 所以我就写了一个算法, 来解决这个问题。

再说一下我的这个非递归算法的思想, 大体思想是这样的:先定义一个类型为BTN指针的数组, 再定义一个变量来标记当前节点。当输入孩子时, 会提示是谁的左孩子或者是谁的右孩子, 从而使输入复杂二叉树变得简单。

(1) 当输入的树为空树时, 也就是第一次输入根节点为零时, 提示二叉树为空, 终止本算法。

(2) 当输入的树不为空树时, 也就是说第一次输入根节点不为零时, 继续输入根结点的左孩子, 指向根节点的指针存入数组, 变量++, 准备存储下一个节点。直到输入左孩子的值为零时, 即当前结点的左孩子为空时, 输入本结点的右孩子。当输入右孩子为零时, 由于输入左孩子需要变量++来存储下一个节点, 所以当输入右孩子为空时, 需要变量--来返回到上一个节点, 来输入上一个节点的右孩子。直到变量等于初始值, 也就是说根节点的右孩子输入完毕, 二叉树初始化完毕。

2 如何更好地实现复杂二叉树的初始化

为了解决这个问题, 我编写了一个算法, 本算法可以使二叉树的初始化更为人性化, 解决了复杂二叉树输入繁琐的问题。一般的二叉树要求用户输入先序序列, 当二叉树很庞大时, 先序就比较复杂, 不利于用户的输入, 二叉树就有可能创建失败。非递归有的要求输入二叉树的广义表形式, 对于一般用户当面临比较复杂庞大的二叉树时, 可能也会创建失败。而对于本算法来说, 二叉树越庞大, 优点就越明显, 可以避免用户输入的数据出错。

首先定义一个全局变量b, 记录是否是第一次输入, 它的作用就是当第一次输入时, 程序提示为根节点, 显得更加人性化, 当第二次输入时提示为谁的左孩子或右孩子, 当面临复杂二叉树的输入时就不会因为二叉树太过庞大而出现输入错误。而且当第一次输入为空时会提示用户此二叉树为空二叉树, 不会再去调用其他的方法。还有一点就是定义局部变量d、e, d为左孩子的深度, e为右孩子的深度, 每输入一次左孩子, 则d加一次, 每输入一次右孩子, 则e加一次, 比较d、e的大小从而确定二叉树的深度, 返回深度。每一次输入节点值时, 会提示用户输的是哪个节点的哪个孩子, 这样当二叉树比较庞大时, 用户就不容易输错, 大大提高了用户输入的效率, 而且不用求二叉树的先序或者广义表形式, 对用户来说既方便又清楚。还有就是空二叉树, 当输入为空二叉树即根结点为空时, 不会再调用其它函数, 直接提示用户二叉树为空, 这样使程序运行更快, 减少了再调用其它函数的时间。

3 结语

二叉树的应用在现实生活中占有很重要的地位, 创建复杂二叉树的算法显得尤为重要, 特别是对高级数据结构, 如族谱、各级关系等的研究, 这些算法都具有一定实用价值。

参考文献