已知後序序周遊序列和中序周遊序列建立二叉樹。

已知後序序周遊序列和中序周遊序列建立二叉樹。 例如

輸入後序周遊序列： 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;
}