给两个数组作为先序遍历和中序遍历，如何构造树？

jy2880668

给两个数组作为先序遍历和中序遍历，如何构造树？

typedef struct node {
  int i;
  struct node* lchild, rchild;
} node, * tree;

。。。劳驾您。

哈哈大侠

看一下数据结构书，里面好象有，清华的那本

jy2880668

里边没有啊！！

stoneboy4000

结果不唯一，就像一个数组进栈出栈顺序那个题目一样，只要会排除就行了

clarkr

如果是数组为什么不用下标表示而用指针呢struct node* lchild, rchild？


先序遍历和中序遍历是输出时访问方法的不同，可用递归或栈实现
如何构造树与访问方法没有必然联系

maloneliu

LZ可能是把逻辑数据结构和物理实现搞混淆了。我们这里谈论应该是逻辑数据结构，而它内部的物理实现可以是完全不同的，可以是链的结构，也可以是数组的机构，也可以是其他的数据结构。这里的数据结构更多的是ADT。
正如clarkr所说的，如何构造树与访问方法没有必然联系。但是对于完全二叉树，我们用数组来实现它，具体的原因你可以自己想想:)

rbjojo

先序遍历、中序遍历、后序遍历是二叉树的访问方式，构造二叉树的是链表，看看数据结构的书，肯定是有的

zjwzjw

二叉树中有一个经典的问题就是，已知给定二叉树的前序遍历序列和中序遍历序列，求其后序遍历序列。采用递归的思想，比较容易解决。代码如下：
/*
a是前序序列
b是中序序列
后序序列将保存在c中
*/
void PostOrder(const char a[], const char b[], char c[], int starta, int startb, int startc, int len)
{
if(len==0) return;
if(len==1) { c[startc] = a[starta]; return; }

c[startc+len-1] = a[starta];//处理树根

int i = startb;
while(b[i]!=a[starta]) ++i;
int leftlen = i - startb;
int rightlen = len - leftlen - 1;
PostOrder(a,b,c,starta+1,startb,startc,leftlen);//构造左子树的PostOrder
PostOrder(a,b,c,starta+leftlen+1,startb+leftlen+1,startc+leftlen,rightlen);//构造右子树的PostOrder
}

void PostOrder(const char a[], const char b[], char c[])
{
int len = strlen(a);
PostOrder(a,b,c,0,0,0,len);
c[len] = '\0';
}

其中有构造的过程，
可以研究一下。。。。。。。

jy2880668

感谢zjwzjw ，以及其他各位！