Question

一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，该二叉树的后序遍历是什么？请给出详细答案．谢

谢谢了 很简单的一题 希望能给我写出步骤来 呵呵

Answer 1

DGEBHFCA
这个是2叉树滴图形
楼主看看哈~

A
/ \
B C
/ \ . \
D E F
. / . /
G. H
后序访问的顺序为
(1)遍历左子树；
(2)遍历右子树；
(3)访问根结点。
所以结果为DGEBHFCA

Answer 2

参数说明:
char* sinorder, int s1, int e1:中序遍历结果,s1为开始位置,e1为结束位置
char* spreorder, int s2, int e2:前序遍历结果,s2为开始位置,e2为结束位置
char* spostorder:后序遍历结果
int& curr:当前写入点位置

void in_pre_postorder(char* sinorder, int s1, int e1, char* spreorder, int s2, int e2 ,char* spostorder, int& curr)
{
char t = spreorder[s2];

spostorder[curr--] = t;

for (int i=s1, k=0; i<=e1; i++, k++)
if (sinorder[i]==t)
break;

if (e1-i>0)//如果有右子树
in_pre_postorder(sinorder, s1+k+1, e1, spreorder, s2+k+1, e2, spostorder, curr);
if (i-s1>0)//如果有左子树
in_pre_postorder(sinorder, s1, s1+k-1, spreorder, s2+1, s2+k, spostorder, curr);
}

Answer 3

1、从前序遍历ABDEGCFH得出A为根节点；
2、从中序遍历DBGEACHF得出DBGE为左子树，CHF为右子树；
3、重复1、2从前序遍历BDEG 中序遍历DBGE 得出左子树的根为B；
依次类推。