已知某二叉树先序遍历序列为ABCDEFH,中序遍历序列是BDCEAHF

Question

已知某二叉树先序遍历序列为ABCDEFH,中序遍历序列是BDCEAHF,写出后序遍历

Answer 1

已知先序和中序，求后序

我们来举个简单的例子，先序序列为：ABDECF，中序序列为：DBEAFC。

算法思想：先序遍历树的规则为中左右，可以看到先序遍历序列的第一个元素必为树的根节点，比如上例中的A就为根节点。再看中序遍历为：左中右，再根据根节点A，可知左子树包含元素为：DBE，右子树包含元素：FC。然后递归的 进行左子树的求解（左子树的先序为：BDE，中序为：DBE），递归的进行右子树的求解（即右子树的先序为：CF，中序为：FC）。如此递归到没有左右子树为止。

先序:(A)BCDEFH

中序:BDCE(A)HF

先序:ABCDEFH

=>A(BCDE)(FH)

=>A(B(CDE))(FH)

=>A(B(C(DE)))(FH)

=>A(B(C(D)(E)))(F(H))

            A

          /   \

        B       F

         \      /

          C   H

        /  \

      D    E

后序为:DECBHFA

#include <stdio.h>
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}

/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e)   return ;                  /* 非法子树，完成。 */

if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}

c=pre[pre_s];  /* c储存根节点。 */

k=find(c,in,in_s,in_e);                  /* 在中序中找出根节点的位置。 */

pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */

pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */

//printf("%c",c);                          /* 根节点输出。 */
cout<<c;
}

int main()
{
char pre[]="ABCDEFH";
char in[]="BDCEAHF";
printf("The result:");
pronum(pre,0,sizeof(in)/sizeof(char)-1,in,0,strlen(pre)-1);

cin.get();

return 0;
}