在之前初步介绍图的文章中,我们得知,图(graph)是表征事物之间关系的一种抽象化表示方法,而基于图的概念,我们将所有的无回路无向图拿出来,给它们一个新的名字——树。
关于树的概念性术语很多,这里我们先就简单的二叉树(一个根至多有两个子树)来进行分析。
这就是一些简单的二叉树,这里A、B、C等我们成为节点。A叫做根节点,它的两个分支是B和C,并且我们称B是一个左子树,C是一个右子树,知道了这些简单的概念,我们就可以初步的探讨一些问题了。
二叉树树作为一种特殊的图,我们也要研究其遍历的方式,正如我们研究一般的图的遍历方式。由于其基本结构包括根、左子树、右子树,所以我们遍历的时候可以改变这三个元素的输出方式来得到不同的遍历顺序。
前序遍历的递归定义:对于一个节点,访问并输出根的信息;按照前序遍历左子树;按照前序遍历右子树。
中序遍历的递归定义:对于一个节点,按照中序遍历左子树;访问输出根的信息;按照中序遍历右子树。
后序遍历的递归定义:对于一个节点,按照后序遍历左子树;按照后序遍历右子树;访问并输出根的信息。
拿上图d举个例子,前序遍历:124536,;中序遍历:425361;后序遍历:452631。
值得注意的是,除了中序遍历,其余两种遍历方式可以推广到k叉树,因为对于中序遍历,每当遍历完左子树,都会访问一次根节点,这样会造成多次重复访问根节点,就谈不上“遍历”这二字了。
而且对于一个给定前(后)序遍历和中序遍历的二叉树,是可以唯一确定的。
那么我们来看一道关于二叉树这三种遍历的题目(Problem source :pku2255)
Description
D / / B E / / A C G / / FTo record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG. She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree. However, doing the reconstruction by hand, soon turned out to be tedious. So now she asks you to write a program that does the job for her!
Input
Output
题目大意:给出一个二叉树的前序遍历、中序遍历,让你输出其后序遍历。
数理分析:根据其定义,三种遍历方式是通过递归生成的,那么现在知道了两种遍历方式,也是可以还原出原来的二叉树的。
举个例子,拿第一组数据来说,前序遍历为DBACEGF,中序遍历为ABCDEFG,那么我们通过前序遍历的定义,可知D是最大的那棵树的根,此时我们再通过中序遍历,ABC在D的左端,是左子树,而EFG在D的右端,为右子树,这样可以初步画一个树。然后我们在找前序遍历的第二个点……最终一定会还原出原来的二叉树。
这里题目要求直接输出后序遍历,那么我们在还原二叉树的同时也能构造出后序遍历。在起始情况中,前序遍历的第一个点作为整棵树的根,是要作为后序遍历的最后一个点的,这是我们再通过中序遍历和前序遍历找到此根下的右子树,我们把右子树看成一个整体,通过前序遍历又能找到一个根,再通过此根和中序遍历,分出左子树和右子树……直到这个根没有子树。
随后构造左子树。
这里之所先找根再找右子树在找左子树,是和后序遍历的递归概念呼应的。
编程实现:通过以上的描述,构造过程本质上是一种递归,也可以说是遍历图我们所熟悉的深搜。
参考代码如下。
#include<iostream> #include<string.h> using namespace std; char preorder[30]; char midorder[30]; char postorder[30]; int len; void travel(int preStar,int preEnd ,int midStar , int midEnd) { if(preStar > preEnd) return; postorder[--len] = preorder[preStar]; //记录根 if(preStar == preEnd) return; int i; for(i = 0;i <= midEnd;i++) if(midorder[i] == preorder[preStar]) break; travel(preStar + i - midStar + 1,preEnd, i + 1, midEnd); //左子树 travel(preStar + 1 , preStar + i - midStar , midStar , i - 1);//右子树 } int main() { while(cin>>preorder>>midorder) { len = strlen(preorder); postorder[len] = '