由前序跟中序遍历序求后序遍历序的设计与实现

（中文）由前序跟中序遍历序求后序遍历序的设计与实现（英文）Thedesignandimplementationofgettingpostordertraversalaccordingtopreorderandinordertraversalofabinarytree蔡智聪摘要：树的遍历问题在应用开发过程中是一个很经典且常遇到的问题，在实际工程中，经常可能需要进行某种遍历充的求解。本文介绍如何由一棵二叉树的前序遍历序和中序遍历序来后序遍历序的设计思路与具体C++实现。首先根据前序遍历序和中序遍历序来建立（还原）出二叉树的原型,文中详细介绍了建立（还原）树的算法及原理。然后再用后后序遍历算法求后序遍历序（一串字符串序列）。关键字：二叉树前序遍历序中序遍历序后序遍历序Binary–Tree,Preordertraversal,inordertraversal,postordertraversal正文：几个术语的介绍：二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。前序遍历序：在对一个树进行前序遍历而得到的一个访问结点的序列。遍历的顺序是：先父结点，然后左子树，然后右子树。中序遍历序：在对一个树进行中序遍历而得到的一个访问结点的序列。遍历的顺序是：先左子树，然后父结点，然后右子树。前序遍历序：在对一个树进行前序遍历而得到的一个访问结点的序列。遍历的顺序是：先左子树，然后右子树，然后父结点。引言：树的遍历问题在应用开发过程中是一个很经典且常遇到的问题，在实际工程中，经常可能需要进行某种遍历充的求解。为了描述和实现的简化，本文中以二叉树来代替为例，并将二叉树的结点抽象成一个字符来代替，在实现运用中可以自己加以灵活变通。问题的引出：那么对于一棵给定的二叉树，如何根据前序遍历序和中序遍历序来求出后序遍历序呢？如图A：ABDCGHEIFJ这样的一棵树的前序遍历序为：ABDGHCEIFJ中序遍历序为：GDHBAEICFJ那么如何求出后序遍历序（GHDBIEJFCA）呢？算法原理及分析：1.先建立还原二叉树。2.对于给定的一棵子树（ST）的前序遍历序（PRET）的第一个字符（记作R）肯定是该子树的根。接着就就确定它的左子树和右子树。3.在该子树（ST）中的中序遍历序（INT）找到字符R,那么中序遍历序在R之前的字符（记作左串：STRL）肯定就是ST的左子树上的所有结点，而中序遍历序在R之后的字符（记作右串：STRR）就是ST的右子树上的所有结点。4.记STRL的长度（结点个数）为NL，那么ST的左子树的前序遍历序跟中序遍历序就分别为：PRET(2,NL)（即PRET的一个子串，从第2个结点开始，长度为NL个，后同）跟STRL。而ST的右子树的前序遍历序跟中序遍历序为：PRET（NL+1,Len(PRET)-NL-1）和STRR。5.问题就转化为前两个子问题，就是分别是ST的左子树跟右子树，这样就可以用递归来实现了。6.当一个子树的前序遍历序和中序遍历序都是一个结点时，那么该子树就是只有一个结点的树。这也就是递归终止的条件了，建立一个子树，并返回上一层。7.现在我拿上面图A来演示下：a)由ABDGHCEIFJ得知该树根就是Ab)由GDHBAEICFJ找到A的位置5，那么左子树的中序遍历序就是前4个了，即GDHB。右子树的中序遍历就是EICFJ.c)ABDGHCEIFJ的（2,4）就是左子树的前序遍历序(BDGH)了，(6,5)就是右子树的前序遍历序(CEIFJ)了。d)因为现在就转化成了(BDGH,GDHB)跟(CEIFJ,EICFJ)这两个子问题（两棵子树的建立）了。e)接递归继续就行了。8.树建立好后，就用递归进行后序遍历得到后序遍历序了，相信这个已经不是难点了，大家可以自己实现了。9.到此算法已经介绍完毕，相信大家应该已经知道如何实现了，现在来看看我给出的一个参考实现版本。具体实现（C++）：//Author:BrainDeveloper2008/11/09#includeiostream#includestringusingnamespacestd;//树的结点structNode{charval;Node*LChild;Node*RChild;};//在字符串中查找字符ch,如何找到返回下标，否则返回-1;intSearch(stringstr,charch){for(inti=0;istr.length();++i)if(str[i]==ch)returni;return-1;}//根据前序和中序遍历序来创建树Node*CreateTree(stringpre,stringin){if(pre==)returnNULL;Node*T=newNode();if(pre.length()==1){T-val=pre[0];}else{charroot=pre[0];intindex=Search(in,root);Node*L=CreateTree(pre.substr(1,index),in.substr(0,index));Node*R=CreateTree(pre.substr(index+1,pre.length()-index-1),in.substr(index+1,in.length()-index-1));T-val=pre[0];T-LChild=L;T-RChild=R;}returnT;}//得到后序遍历序并输出voidPrePostTree(Node*Root){if(Root-LChild!=NULL){PrePostTree(Root-LChild);}if(Root-RChild!=NULL){PrePostTree(Root-RChild);}coutRoot-val;}//主函数（测试模块）intmain(){stringpre,in;while(cinprein){Node*T=CreateTree(pre,in);PrePostTree(T);coutendl;}}问题总结：其实这个问题关键在于分析前序遍历充跟中序遍历充的遍历结构特点，借助递归思想，从而将大问题分解成二个子问题，这就是分治的思想，大则分而治之，这是算法设计的一个重要而且常用的思想！在实际工程中，可以将树的结点实例化成需要的类型灵活应用。