求一个二叉树算法

从二叉树的前序遍历和中序遍历，求得后序遍历
例如:
前序遍历:ABD$CE
中序遍历:DB$AEC
求得：
后序遍历：D$BECA
$表示空

[此贴子已经被作者于2006-5-21 13:10:04编辑过]

----------------解决方案--------------------------------------------------------
不懂，估计唯有根据前序和中序建树，然后按后续打印，和预计的比较
----------------解决方案--------------------------------------------------------
是啊，根据前序和中序建树
----------------解决方案--------------------------------------------------------

这样可以吧

# include <stdio.h>
# include <stdlib.h>

struct btnode
{
int data,y;
struct btnode *lchild,*rchild;
};
struct btnode *CreateTree(struct btnode *bt,int c[],int x,int b[])
{
struct btnode *p1,*p2,*q;
int i,j,k;
p1=bt;

for(j=0;j<x;j++)
{
q=(struct btnode *)malloc(sizeof(struct btnode));
q->data=b[c[j]];q->y=c[j]; q->lchild=q->rchild=NULL;
p1=bt;
if(p1==NULL) bt=p1=q;
else
{
while(p1)
{
p2=p1;
if(c[j]<p1->y)
{p1=p2->lchild;k=1;}
else
{p1=p2->rchild;k=0;}
}
if(k==1) p2->lchild=q;
else p2->rchild=q;
}
}
return(bt);
}

void bianli1(struct btnode *t) /* 递归先序遍历 */
{
if (t!=0)
{printf("%d ",t->data);

bianli1(t->lchild);
bianli1(t->rchild);
}
return;
}

void bianli2(struct btnode *t) /* 递归后序遍历 */
{
if (t!=0)
{

bianli2(t->lchild);

bianli2(t->rchild);
printf("%d ",t->data);
}
free(t);
return;
}

main()
{
int a[7]={1,2,4,5,3,6,7}, b[7]={4,2,5,1,6,3,7}, c[7];
int i,j,x,k;
struct btnode *bt=NULL;
for(i=0;i<7;i++)
{
for(j=0;j<7;j++)
if(a[i]==b[j])
{
k=j;
break;
}
c[i]=k;
}

bt=CreateTree(bt,c,7,b);
bianli1(bt);
printf("\n");
bianli2(bt);

getch();
}

不知道楼主有没有奖励

----------------解决方案--------------------------------------------------------
天气热，送你块消暑
多谢了
----------------解决方案--------------------------------------------------------
数组c[]用得相当玄啊，能否贴个算法出来 SunShining
----------------解决方案--------------------------------------------------------
利用我发给 "论坛" 的二叉树排序.

c[]用来记忆数组b[]的位置..

然后 按位置进行二叉树排序.

别的我不用说了吧..你应该明白吧
----------------解决方案--------------------------------------------------------
当然.数组b[]的位置是由数组a[]产生的~
----------------解决方案--------------------------------------------------------

这个我明白，但是为什么这样创出来的二叉树是对的（是不是钻牛角尖了？）
我想明白原理，但现在还不能从程序中看出原理,主要是数组c[]

----------------解决方案--------------------------------------------------------

简单点..
我们先不认为下标从0开始
a[1]=1 1=b[4] c[1]=4
a[2]=2 2=b[2] c[2]=2
a[3]=4 4=b[1] c[3]=1
...以此类推

最后c[1]-c[7]为 4 2 1 3 6 5 7

有了这个结果.去拿笔算算
用二叉树排序建立个二叉树.看看结果.
这是个算法.不是什么原理!

----------------解决方案--------------------------------------------------------