Question

已知一棵二叉树的先序遍历序列为：ABDCE，中序遍历序列为：BDAEC，请画出这棵二叉树

已知一棵二叉树的先序遍历序列为：ABDCE，中序遍历序列为：BDAEC，请画出这棵二叉树，并给出其后序遍历序列。
谢谢唔~我不确定自己写的对不对

Answer 1

这个是你要找的吗？

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

typedef struct BiTNode{
    char e;
    struct BiTNode *lchild,*rchild;
}BiTNode;

void preOrderTravse(BiTNode *T1){
    if(T1){
        printf("%c",T1->e);
        preOrderTravse(T1->lchild);
        preOrderTravse(T1->rchild);
    }
}
void inOrderTravse(BiTNode *T1){
    if(T1){
        inOrderTravse(T1->lchild);
        printf("%c",T1->e);
        inOrderTravse(T1->rchild);
    }
}
void postOrderTravse(BiTNode *T1){
    if(T1){
        postOrderTravse(T1->lchild);
        postOrderTravse(T1->rchild);
        printf("%c",T1->e);
    }
}
int CreateBiTree(BiTNode **T1,char *preString,char *inString,int start,int end){
    if(start==end){
        *T1=NULL;
    }
    else{
        *T1=(BiTNode*)malloc(sizeof(BiTNode));
        int middle=start;
        while(inString[middle]!=*preString) middle++;
        (*T1)->e=*preString;
        preString++;
        CreateBiTree(&((*T1)->lchild),preString,inString,start,middle);
        preString+=middle-start;        //特别注意这一点：不是加middle，而是加middle-start!
        CreateBiTree(&((*T1)->rchild),preString,inString,middle+1,end);
    }
    return 1;
}
int main(){
    /*
    char preString[]="ABECDFGHIJ",inString[]="EBCDAFHIGJ";
    */
    //更通用的方法：
    char *preString,*inString;
    char pre[50],in[50];
    preString=pre;
    inString=in;
    printf("请输入前序序列：");
    gets(preString);
    printf("请输入中序序列：");
    gets(inString);
    //
    int start=0,end=0;
    end=strlen(preString);      //start、end是指当前inString串的起始与结束
    BiTNode *T1;
    CreateBiTree(&T1,preString,inString,start,end);
    preOrderTravse(T1);
    printf("\n");
    inOrderTravse(T1);
    printf("\n");
    postOrderTravse(T1);
    return 0;
}

参考：http://www.itnose.net/detail/6212347.html

Answer 2

二叉树根节点为A，A的左节点为B，B的右节点为D，A的右节点为C，C的左节点为E
后序遍历序列为DBECA