已知二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是？

已知二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是？

二叉树的后序遍历序列是DACBE, 中序遍历序列是DEBAC

根据后序DACBE最后的字符是E, 可以确定E是根结点.
那么,中序DEBAC就以E为中心, D为根结点的左子树, BAC是根结点的右子树.

      E
     / \
    D   BAC

后序DACBE里的B在E之前, 中序DEBAC里的B在E之后, 可以确定B是E的右孩子.

      E
     / \
    D   B
         \
          AC

后序DACBE里的A跟着D之后, 预计A在二叉树的最后, 那么C层次上应该在B和A之间.
二叉树的示意图如下:

      E
     / \
    D   B
         \
          C
         /
        A

所以, 前序遍历序列是 EDBCA


C语言测试程序
测试结果:

创建二叉树,输入前序扩展序列: ED##B#CA###
前序遍历序列: E D B C A
中序遍历序列: D E B A C
后序遍历序列: D A C B E

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    char data;
    struct Node *lchild;
    struct Node *rchild;
}Bitree;
//用"前序遍历"算法创建二叉树
void CreateBiTree(Bitree **bt)
{
    char s;
    scanf("%c",&s); //输入数据
    if(s=='#')      //'#'是空节点
        *bt=NULL;
    else
    {
        *bt=(Bitree *)malloc(sizeof(Bitree));
        (*bt)->data=s;
        CreateBiTree(&((*bt)->lchild));
        CreateBiTree(&((*bt)->rchild));
    }
}
//前序遍历
void preOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        printf("%c ",ptr->data);
        preOrder(ptr->lchild);
        preOrder(ptr->rchild);
    }
}
//中序遍历
void inOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        inOrder(ptr->lchild);
        printf("%c ",ptr->data);
        inOrder(ptr->rchild);
    }
}
//后序遍历
void postOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        postOrder(ptr->lchild);
        postOrder(ptr->rchild);
        printf("%c ",ptr->data);
    }
}

int main()
{
    Bitree *root;
    printf("创建二叉树,输入前序扩展序列: ");
    CreateBiTree(&root);

    printf("前序遍历序列: ");
    preOrder(root);
    printf("\n中序遍历序列: ");
    inOrder(root);
    printf("\n后序遍历序列: ");
    postOrder(root);

    printf("\n");
    return 0;
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息