注册 登录
编程论坛 C++教室

求二叉树的前序遍列!

雪色朝阳 发布于 2010-03-18 17:46, 896 次点击
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!


[ 本帖最后由 雪色朝阳 于 2010-3-19 10:08 编辑 ]
8 回复
#2
qlc002010-03-18 18:20
你的这道题就有问题,没有那样的二叉树!
#3
smltq2010-03-19 08:49
ab绝对有问题
#4
玩出来的代码2010-03-19 13:57
在后序中找中序序列中的字符在后序中最右边的字符,,
中序DEBAC,后序DACBE,
第一个字符E,                                        先序  E
此时中序分为D,BAC两部分,再看左子树一个D,                 ED
右子树BAC找到B,                                           EDB
。。。得先序为EDBCA
#5
雪色朝阳2010-03-19 14:28
回复 4楼 玩出来的代码
还是不懂,可以说一下做这类题的方法吗?
#6
玩出来的代码2010-03-19 15:03
程序代码:
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;
}
找了一段程序,你看看,这种题……,也就只是根据中序后序构造先序,或是根据先序中序构造后序……
#7
smltq2010-03-19 15:14
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!
已知二叉树的后序和中序,可以确定一课树,这课树为:
         E
     D        B
           C     
        A
所以,它的前序为:EDBCA


[ 本帖最后由 smltq 于 2010-3-19 15:17 编辑 ]
#8
chsteven2010-03-19 15:38
以下是引用smltq在2010-3-19 15:14:13的发言:

已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!已知二叉树的后序和中序,可以确定一课树,这课树为:
         E
     D        B
           C     
        A
 ...
你上面这个树的中序是DEBAC吗?
#9
smltq2010-03-19 16:55
        E
    D      B
             C
           A

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