文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
已知二叉树的前序遍历和后序遍历，求二叉树的后序遍历。算法很简单，由前序遍历的第一个元素可确定左、右子树的根节点，参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列，最终构造出二叉树。自己写了一段C语言的数组版，加了注释，应该很好理解。
由二叉树的前序遍历和中序遍历序列能唯一确定一棵二叉树。
前序遍历为：访问根节点、访问左子树、访问右子树；
中序遍历为：访问左子树、访问根节点、访问右子树。
后序遍历为：访问左子树、访问右子树、访问根节点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <stdio.h> #include <string.h> char preord[100],inord[100]; void rebuild(int preleft,int preright,int inleft,int inright) { int root,leftsize,rightsize; if(preleft<=preright&&inleft<=inright) { //在中序遍历中寻找根节点 for(root=inleft;root<=inright;root++) { if(preord[preleft]==inord[root]) break; } //计算左右子树大小 leftsize=root-inleft; rightsize=inright-root; //如果有左子树则递归重建左子树 if(leftsize>0) { rebuild(preleft+1,preleft+leftsize,inleft,root-1); } //如果有右子树则递归重建右子树 if(rightsize>0) { rebuild(preleft+leftsize+1,preright,root+1,inright); } //如果无子树则打印根节点 printf("%c",inord[root]); } } int main() { int length; scanf("%s%s",preord,inord); length=strlen(preord)-1; rebuild(0,length,0,length); return 0; } |
转载请注明：Slyar Home » 求二叉树的后序遍历 C语言 数组实现
