创建二叉树的非递归算法设计与分析.pdf

《创建二叉树的非递归算法设计与分析.pdf》由会员分享，可在线阅读，更多相关《创建二叉树的非递归算法设计与分析.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第23卷第3期Vol.23 No.3荆门职业技术学院学报Journal of Jingmen Technical College2008年3月Mar.2008收稿日期 2008-01-07基金项目河南省教育科学“十五”规划重点课题(项目编号:2005-JKGHAZ-141)。作者简介王仲英(1969-),男,甘肃天水人,济源职业技术学院副教授,硕士。研究方向:应用数学。E-mail:;刘秋菊(1970-),女,济源职业技术学院副教授。研究方向:计算机网络与软件理论;裴利军(1972-),男,郑州大学讲师,博士。研究方向:应用数学与算法分析。创建二叉树的非递归算法设计与分析王仲英1,刘秋菊1,裴

2、利军2(1济源职业技术学院 教务处,河南 济源 454650;2郑州大学 数学系,河南 郑州 450002)摘 要 通过仔细分析二叉树的递归创建过程,借助堆栈、完全二叉树的概念和二叉树的顺序存储来实现非递归算法,并对算法进行了分析。使执行过程不依赖于函数或过程的重复调用,有更大的灵活性,可以应用在程序与软件设计中。关键词 二叉树;递归算法;非递归算法;完全二叉树中图分类号TP311.12文献标识码A文章编号1008-4657(2008)03-0050-06二叉树是计算机科学中一种非常重要的数据结构1-3,有着广泛的应用,许多实际问题抽象出来的数据结构往往是二叉树的形式,为了便于对二叉树进行操作

3、,在计算机内部常采用二叉链表的形式存储二叉树。理解并掌握好二叉链表的创建过程就显得非常重要了。1 问题的提出4 要应用二叉链表来解决实际问题,首先我们必须学会创建一个二叉链表,在各类算法与数据结构教材以及参考书上常采用的算法是:按先根遍历的顺序输入结点的信息,递归生成一棵二叉链表存储的二叉树。具体实现算法如下:BinTreeNode createBTree()/3 递归创建从根结点开始的二叉树 3/BinTreeNode3bnode;char ch;cin ch;if(ch=)bnode=NULL;/输入结点的信息,输入 结束else bnode=new BinTreeNode;if(bnod

4、e=NULL)cout data=ch;bnode-lchild=createBTree();/3 递归构造左子树 3/bnode-rchild=createBTree();/3 递归构造右子树 3/return bnode;05 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/在理解上述递归函数时,一般来说是有一定难度的。因为程序设计人员要用堆栈这种数据结构来实现函数递归调用,数据元素的进栈和出栈是非常重要的操作,总是很难理解递归算法生成二叉树的过程。为了理解好这个算

5、法以及递归生成二叉树的过程,我们有必要采用非递归的方法来生成一棵二叉树;同时我们知道,在程序设计中,递归算法可以有效简化某些特殊问题的编程,但它只能简化程序编码,不能降低程序的时间和空间复杂度。相反,由于执行过程依赖函数或过程的重复调用,会带来附加的时间消耗。而且由于保存函数调用的返回地址需要占用系统栈,从而增加了执行的空间复杂度,也限制了问题的处理规模。本文给出三种创建二叉树的非递归算法,这三种非递归算法在时间与空间效率上均优于递归算法,而且不使用系统栈,执行过程不依赖于函数或过程的重复调用,有很大的灵活性,可以应用在程序或软件设计中,也可给程序设计人员提供一种解决问题的思路或方法。2 问题

6、的分析例如要创建的二叉树如图1所示,对创建二叉树的递归过程进行分析,表1列出了对图1中的二叉树在创建过程中栈的变化情况。表1 创建二叉树时栈的变化情况序号访问元素栈的内容说明1AAA入栈2BA BB入栈,作为A的左子树3#AB的左子树为空,B出栈4A BB入栈5DA B DD入栈6#A BD的左子树为空,D出栈7A B DD入栈8#A BD的右子树为空,D出栈9AB出栈10A出栈11AA入栈12CA CC入栈13EA C EE入栈14#A CE的左子树为空,E出栈15A C EE入栈16#A CE的右子树为空,E出栈17AC出栈18A CC入栈19#AC的右子树为空,C出栈20A出栈 从表1可

7、知,在递归创建二叉树时,每次创建完当前结点就转向该结点的左子树继续执行,当该结点的左子树创建完后,再转向该结点的右子树继续执行。每个结点有两次入栈和两次出栈的过程。3 问题的解决解决问题的方法一:通过分析,采用非递归算法来创建一棵二叉树时5,我们参照递归过程中栈的变化情况适用堆栈15 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/图1 一般二叉树(左)及扩展二叉树(右)来解决6。首先将二叉树进行扩展,如图1所示,然后按先根遍历的顺序输入结点的信息,根据输入的信息设置一

8、个标志位flag,如果flag=0,创建当前结点的左孩子结点,如果flag=1,创建当前结点的右孩子结点,可分以下情况进行处理。1)当前要创建的结点值为#并且flag=1,说明当前结点的父结点左右孩子结点处理结束,应将栈顶结点出栈。如果出栈的结点依然等于栈顶结点的右孩子,说明当前栈顶结点的左右孩子结点也处理结束,栈顶结点继续出栈。直到当前栈顶结点的右孩子结点不等于出栈的结点为止。2)当前要创建的结点值为#并且flag=0,则置flag=1,当前结点的左孩子创建结束,转向创建右孩子。3)当前要创建的结点值不为#并且flag=0,创建当前结点并作为栈顶结点的左孩子,同时将当前结点入栈。4)当前要创

9、建的结点值不为#并且flag=1,创建当前结点并作为栈顶结点的右孩子,同时将当前结点入栈,然后置flag=0,转向左孩子结点的创建。具体算法实现如下:BinTreeNode CreateBTree()/3 使用栈,按照先根遍历的顺序来生成一棵二叉树 3/char ch20;BinTreeNode3head,3P,3t,3stack50;/3stack50 为堆栈 3/int i=0,top=0;/3top为栈顶指针 3/int flag=0;/3 标志位 3/cin ch;/3 对扩充二叉树按照先根遍历的顺序输入结点的信息 3/if(ch i=#)return NULL;P=new BinTr

10、eeNode;if(P=NULL)return NULL;P-data=ch i;P-lchild=NULL;P-rchild=NULL;stack top =P;top+;i+;head=P;while(i rchild=t)top-;t=stack top;else if(ch i=#&flag=0)/3 第二种情况 3/flag=l:elseP=new BinTreeNode;if(P=NULL)retum NULL;25 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.ht

11、tp:/P-data=ch i;P-lchild=NULL;P-rchild=NULL;if(flag=0)/3 第三种情况 3/stack top-1 -lchild=P;stack top =P;top+;else/3 第四种情况 3/stack top-1 -rchild=P;flag=0;stack top =P;top+;i+;return head;程序运行:输入:AB#D#CE#调用该非递归算法即可建立一棵二叉树。解决问题的方法二:用完全二叉树的概念非递归地创建二叉树。完全二叉树具有如下性质。如果对一棵有n个结点的完全二叉树按层次次序从1开始编号,则对任一结点i有:1)若i=1,

12、序号为i的结点是根;若i 1,则其双亲结点是i/2。2)若2i n,序号为i的结点无左孩子。3)若2i+1 n,序号为i的结点无右孩子。根据以上性质我们可以知道:已知某结点在数组中存储的下标可以很容易的找到它的左孩子和右孩子在数组中的下标位置,例如结点A,它在数组中的下标为1,根据性质可知,如果它的左、右孩子存在,则它的左孩子在数组的下标为231=2,它的右孩子在数组中的下标为231+1=3。如果二叉树中每个结点的数据和对应完全二叉树的结点编号一致,如图2所示。图2 一般二叉树的编号非递归创建二叉树的算法如下:BinTreeNode3PMAX;/3 辅助向量 3/BinTreeNode3Cre

13、ateBTree()int i;char ch;BinTreeNode3s,3head;cin i ch;while(i!=0&ch!=#)/3 输入结束标志 3/s=new BinTreeNode;s-data=ch;s-lchild=s-rchild=NULL;p i=s;if(i=1)head=s;/head指向根结点35 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/else int j=i/2;if(i%2=0)p j-lchild=s;/s是编号为i的左孩

14、子else p j-rchild=s;/s是编号为i的右孩子cin i ch;return head;运行时只需输入每个结点的编号和数据,以输入0和#作为输入的结束标志。创建时要注意:必须先创建根结点,然后再创建其他结点。解决问题的方法三:方法二是根据完全二叉树的编号以及特点来解决问题的7,方法三是使用队列,按照层次次序来创建一棵二叉树。先将该二叉树扩充为完全二叉树,然后再按层次次序依次存储到数组单元中,即对该二叉树采用顺序存储,如图3所示。图3 二叉树转变为完全二叉树以及二叉树的顺序存储具体实现时可以将二叉树的顺序存储数组作为一个队列,f是指向队列的头指针,r是指向队列的尾指针。步骤如下:1

15、)将一棵二叉树扩充为一棵完全二叉树。2)将完全二叉树的各个结点的地址而不是结点值按层次次序依次存储到数组单元中,如果为虚结点则它的地址为空(NULL或),每存入一个结点的地址则队列的尾指针加1。3)第i个元素出队,头指针f加一,同时在数组中找出该元素的左孩子和右孩子(如果存在则它们分别在数组的23i和23i+1的位置上)。将第i个元素的左孩子指针域指向23i,它的右孩子指针域指向23i+1。4)重复执行第(3)步直到队列中元素个数为空,即头指针与尾指针相等。具体实现算法如下:BinTreeNode CreateBTree()char ch20;BinTreeNode3head,3p,3Q20/

16、head保存二叉树的根,Q为队列int i=O,n,f=l,r=1;/f为队列的头指针,r为队列的尾指针cin ch;n=strlen(ch);while(1)if(ch i=0)break;if(ch i=3)p=NULL;/为虚结点,在数组中存储空值else p=new BinTreeNode;if(p=NULL)/申请结点空间 cout data=ch i;p-lchild=NULL;p-rchild=NULL;45 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:

17、/Q r+=p;/p结点入队,尾指针加1if(i=0)head=p;/当前结点是根结点i+;while(f!=r)/队列不空 p=Q f;if(p!=NULL)if(23f lchild=Q23f;/左指针域指向左孩子if(23f+l rchild=Q23f+l;/右指针域指向右孩子 3/f+;/对头指针加1,当前结点出队return head;程序运行:输入:ABC3DE程序运行正常,创建二叉树结束。因为根据先根和中根遍历可以唯一地确定一棵二叉树,可以调用二叉树的先根和中根遍历算法来验证算法的正确性。4 结束语在这里我们成功地借助堆栈和完全二叉树实现了将一个递归算法转换为非递归的算法,这对于

18、理解二叉树的创建非常清晰,同时完全二叉树具有一般二叉树不具备的特点,利用完全二叉树的概念还可以解决二叉树的图形处理、二叉树的查找等在程序设计中具有特别重要的意义的问题。二叉树也是计算机中对树的应用的一种简单情况,以上讨论是在教学过程中的经验和总结。参考文献1严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,1998.2张乃孝.算法与数据结构Ml.北京:高等教育出版社,2002.3李春葆,曾 惠,张植民.数据结构程序设计题典M.北京:清华大学出版社,2002.4孟 林,尹德辉.二叉树遍历递归算法非递归化的讨论J.福建电脑,2004(6):30-31.5霍红卫,许 进.快速排序算法研究J.微电子学

19、与计算机,2002(6):6-9.6朱玉龙,任文岚.五皇后问题与伴随序列法J.小型微型计算机系统,2000,21(11):1 221-1 222.7吴福英,谭罗生,王明文.顺序存储的满二叉树中序遍历J.江西师范大学学报,2003(8):372-375.Design and Analysis of Creating the Non-recursive Algorithm of Two Forks TreeWANG Zhong-ying,et al.(Jiyuan Vocational and Technical College,Jiyuan,Henan,454650,China)Abstract

20、:This article analysis process of creating two forks tree,with the aid of stack completely two forks tree concept andsequence storge to realize non-recursive algorithm,and carrieson analysis to its algorithm,and doesnt depend on function orpro2cedure process.It can be used in designing programs and soft ware.Key words:t wo forks tree;recursive algorithm;non-recursive algorithm;completely two forks tree55 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/