由后序和中序遍历恢复二叉树的算法.pdf.pdf

第32卷?第6期 2010年12月武汉理工大学学报?信息与管理工程版 JOURNALOFWUT(INFORMATION&MANAGEMENTENGINEERING) 文章编号:1007-144X(2010)06-0910-04 文献标志码:A 由后序和中序遍历恢复二叉树的算法李?昆 1,王卫华 2 (,江西南昌330063;,湖北武汉430070) 摘?要:针对如何由二叉树的遍历序列恢复二叉树的问题,提出了由后序遍历和中序遍历唯一确定一棵二叉树的算法,分别用递归和非递归两种方法进行了描述,并在TurboC中实现了算法。关键词:后序遍历;中序遍历;二叉树中图分类号:TP312???? DOI:/.- 收稿日期:2010-05-06. 作者简介:李?昆(1978-),女,湖北广水人,南昌航空大学数学与信息科学学院讲师. ??二叉树是数据结构中一种重要的存储结构, 但在文献[1]及相关的文献中,对于如何由遍历序列恢复二叉树都没有进行详细的介绍,更没有相关算法的描述;而由二叉树的遍历序列来恢复一棵二叉树又是很重要的,例如由逆波兰式和中缀式来确定波兰式就是一个很典型的应用[2]。由二叉树的递归定义可知[3],二叉树由3个基本单元组成:根结点、左子树和右子树。因此, 若能依次遍历这3部分,便是遍历了整棵二叉树。若限定先左后右,则有先序遍历、中序遍历和后序遍历3种遍历方式[4]。基于二叉树的递归定义, 可以很容易地得到遍历二叉树的递归算法[5]。在实际应用中由二叉树的遍历序列来唯一确定一棵二叉树,至少需知道两种遍历序列,即后序遍历序列和中序遍历序列[6]。 1?后序和中序遍历序列的递归算法根据后序遍历和中序遍历的递归算法,可以证明这两种遍历组合也可以唯一确定一棵二叉树[7]。具体步骤如下: (1)如果后序和中序遍历序列都为空,则该二叉树是空树。(2)对于有n(n 1)个结点的二叉树,把后序遍历序列中的最后一个结点作为该二叉树的根结点。(3)在中序遍历序列中找到根结点,记录该结点的位置n。(4)在中序遍历序列中根结点前面的n-1 个结点序列就是根结点左子树的中序遍历序列; 在中序遍历序列中根结点后面的结点序列就是根结点右子树的中序遍历序列。(5)在后序遍历序列中前n-1个结点序列就是根结点左子树的后序遍历序列;在后序遍历序列中后面的结点(除根结点)则是根结点右子树的后序遍历序列。(6)以此类推重复步骤(2)~步骤(5)就可以由后序遍历序列和中序遍历序列唯一确定。程序代码如下: typedefstructnode {chardata; structnode*lchild,*rchild; }bitree; bitree* restoretree(char* inlis,tchar* postlis,tinti,intj,intk,intl) {intn; bitree*p; p=(bitree*)malloc(sizeof(bitree)); p->data=*(postlist+l);/*从后序遍历序列中读取结点信息*/ n=i; for(;(*(inlist+n)!=*(postlist+l));n ++