已知后序序遍历序列和中序遍历序列建立二叉树。

已知后序序遍历序列和中序遍历序列建立二叉树。 例如

输入后序遍历序列： FGDBCA， 再输入中序遍历序列： BFDGAC，则 输出该二叉树的先序遍历序列： ABDFGC。

具体过程和上一个文章里的先序和中序确定二叉树一样

不明白的可以直接移步上一篇

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode {
    ElementType data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, * BiTree;

BiTree CreatBinTree(char* post, char* in, int n);
void preorder(BiTree T);

int main()
{
    BiTree T;
    char postlist[100]="FGDBCA";
    char inlist[100]="BFDGAC";
    int length;
    length = strlen(postlist);
    T = CreatBinTree(postlist, inlist, length);
    preorder(T);
    return 0;
}
void  preorder(BiTree T)
{
    if (T)
    {
        printf("%c", T->data);
        preorder(T->lchild);
        preorder(T->rchild);

    }
}
BiTree CreatBinTree(char* post, char* in, int n)
{
    BiTree T;
    int i;
    if (n <= 0) return NULL;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = post[n - 1];
    for (i = 0; in[i] != post[n - 1]; i++);
    T->lchild = CreatBinTree(post, in,i);
    T->rchild = CreatBinTree(post+i,in+i+1,n-1-i);
    return T;
}