二叉树的已知后序中序求先序算法

Question

要用C语言函数，且程序中要有算法 最好有解释 跪求！！！

Answer 1

/* 树中已知中序和后序求先序。
如中序为：bdac 后序为：dbca
则程序可以求出先序为：abdc 。此种题型为数据结构常考题型。
算法思想：后序遍历树的规则为左右中，则说明最后一个元素必为树的根节点，比如上例
中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含
元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的
进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右
子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。

表达不很清楚，希望自己实践理解。
2004.12.4
*/
#include <stdio.h>
#include<string.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;
}

/* 其中pro[]表示后序，pro_s为后序的起始位置，pro_e为后序的终止位置。 *//* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pernum()求出pro[pro_s～pro_e]、in[in_s～in_e]构成的先序序列。 */
void pernum(char pro[],int pro_s,int pro_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]); /* 子树子仅为一个节点时直接输出并完成。 */<br> return ;<br> }
c=pro[pro_e]; /* c储存根节点。 */
printf("%c",c); /* 根节点输出。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pernum(pro,pro_s,pro_s+k-1-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pernum(pro,pro_s+k-in_s,pro_e-1,in,k+1,in_e); /* 递归求解分割的右子树。 */
}

int main()
{
char in[]="debac";
char pro[]="ebcad";

printf("The result:");
pernum(pro,0,strlen(in)-1,in,0,strlen(pro)-1);
return 0;

}