已知二叉树的先序遍历序列为ABCDEFG,中序遍历序列为AHIFCJGDEBD，其后序遍历序列为______

Question

已知二叉树的先序遍历序列为ABCFHIDGJE,中序遍历序列为AHIFCJGDEB，其后序遍历序列为______

Answer 1

先序遍历序列为ABCFHIDGJE, 中序遍历序列为AHIFCJGDEB

[先序]第1个字符是A,这是根节点,而[中序]第1个字符也是A,表明根节点A没有左子树,而只有右子树.
[先序]第2个字符是B,表明B紧跟A的后面,是A的右分支,而[中序]的B排在末尾,表明B只有左子树,
而没有右子树.
[先序]第3个字符是C,表明C紧跟B的后面,是B的左分支,而[中序]的C的前面有"HIF",后面有"JGD...",
预计C会有左子树,也应该有右子树.

二叉树示意图:

      A
       \
        B
       /
      C
    /    \
   F      D
  /      / \
 H      G   E
  \    /
   I  J

后序遍历序列 I H F J G E D C B A


// C语言测试代码
// 测试结果:
// 创建二叉树,输入先序扩展序列(#表示空结点):
// A#BCFH#I###DGJ###E###
// 先序遍历序列: A B C F H I D G J E
// 中序遍历序列: A H I F C J G D E B
// 后序遍历序列: I H F J G E D C B A

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

typedef struct Node
{
    char data;
    struct Node* left;
    struct Node* right;
}Node,*TreeNode;

//创建二叉树: 先序扩展序列 + 递归法
void CreateBiTree(TreeNode *pRoot)
{
    char input;
    scanf("%c",&input); //输入数据
    if(input == '#')    //#是空结点
    {
       *pRoot = NULL;
    }
    else
    {
        *pRoot=(TreeNode)malloc(sizeof(Node));
        if(*pRoot == NULL)
        {
            printf("\n分配动态内存时出错.\n");
            exit(1);
        }
        (*pRoot)->data=input;
        CreateBiTree(&((*pRoot)->left));
        CreateBiTree(&((*pRoot)->right));
    }
}
//先序遍历
void PreOrder(TreeNode root)
{
    if(root != NULL)
    {
        printf("%c ",root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}
//中序遍历
void InOrder(TreeNode root)
{
    if(root != NULL)
    {
        InOrder(root->left);
        printf("%c ",root->data);
        InOrder(root->right);
    }
}
//后序遍历
void PostOrder(TreeNode root)
{
    if(root != NULL)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%c ",root->data);
    }
}

int main()
{
    TreeNode root;

    printf("创建二叉树,输入先序扩展序列(#表示空结点):\n");
    CreateBiTree(&root);

    printf("先序遍历序列: ");
    PreOrder(root);
    printf("\n");
    printf("中序遍历序列: ");
    InOrder(root);
    printf("\n");
    printf("后序遍历序列: ");
    PostOrder(root);
    printf("\n");

    return 0;
}