已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，如何求他的前序遍列？请详细说明！谢谢！


[ 本帖最后由 雪色朝阳 于 2010-3-19 10:08 编辑 ]

你的这道题就有问题，没有那样的二叉树！

ab绝对有问题

在后序中找中序序列中的字符在后序中最右边的字符，，
中序DEBAC，后序DACBE，
第一个字符E，                                        先序  E
此时中序分为D，BAC两部分,再看左子树一个D，                 ED
右子树BAC找到B，                                           EDB
。。。得先序为EDBCA

还是不懂，可以说一下做这类题的方法吗？

BiTree CreatBT(char *in,char *post,int n,int m)
{                                //in中序序列，post后序n中序的个数m长度
    char *p,*q,*maxp;
    int maxin,w,r;
    BiTree T;
    r=-1;
    if(n<=0) return NULL;        //思想：在后序中找中序序列中的字符在后序中最右边的字符
    for(p=in;p<in+n;p++)
      for(q=post;q<post+m;q++)
      {
          if(*p==*q)
          {
              w=q-post;
              if(w>r)
              {
                  r=w;              //保存后序中的字符的位置
                  maxp=p;           /*保存找到的字符为递归右子树准备*/
                  maxin=p-in;       /*递归左子树准备*/
              }
          }
      }
    T=(BiTree)malloc(sizeof(BNode));
    T->data=post[r];
    T->lchild=CreatBT(in,post,maxin,m);
    T->rchild=CreatBT(maxp+1,post,n-maxin-1,m);
    return T;
}

找了一段程序，你看看，这种题……,也就只是根据中序后序构造先序，或是根据先序中序构造后序……

已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，如何求他的前序遍列？请详细说明！谢谢！

已知二叉树的后序和中序，可以确定一课树，这课树为：
         E
     D        B
           C     
        A
所以，它的前序为：EDBCA


[ 本帖最后由 smltq 于 2010-3-19 15:17 编辑 ]

你上面这个树的中序是DEBAC吗？

        E
    D      B
             C
           A

sorry,前面偶把树画错了……