已知一棵二叉树的层次遍历序列ABCDEFG，中序遍历为BAFGDCE，则这个二叉树怎么画？

Question

已知一棵二叉树的层次遍历序列ABCDEFG，中序遍历为BAFGDCE，则这个二叉树怎么画？(T＿T)我画到DEFG就蒙了……

Answer 1

根据 层次遍历序列ABCDEFG, 中序遍历序列BAFGDCE, 得到的二叉树是:

     A
   /  \
  B    C
      / \
     D   E
    /
   F
    \
     G

先序遍历序列: ABCDFGE
中序遍历序列: BAFGDCE
后序遍历序列: BGFDECA
层次遍历序列: ABCDEFG


如果是如下形状的二叉树,则
层次遍历序列仍然是ABCDEFG,但是,中序遍历序列是BAFDGCE (D,F,G的结构不同了)
     A
   /  \
  B    C
      / \
     D   E
    / \
   F   G


// C代码测试程序
// 输入先序扩展序列: AB##CDF#G###E##
// 输出4种遍历结果
// 先序遍历序列: ABCDFGE
// 中序遍历序列: BAFGDCE
// 后序遍历序列: BGFDECA
// 层次遍历序列: ABCDEFG
//
// 二叉树示意图:
//     A
//   /  \
//  B    C
//      / \
//     D   E
//    /
//   F
//    \
//     G
//
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef int bool;

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode, *BiTree;

typedef BiTNode * QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode * next;
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitQueue_L(LinkQueue *Q)
{
    (*Q).front = (QueuePtr) malloc (sizeof(QNode));
    if ((*Q).front == NULL)
        return OVERFLOW;
    (*Q).front->next = NULL;
    (*Q).rear = (*Q).front;
    return OK;
}

bool QueueEmpty_L(LinkQueue Q)
{
    return (Q.front == Q.rear);
}

Status EnQueue_L(LinkQueue *Q, QElemType e)
{
    QNode *s = (QNode *) malloc (sizeof(QNode));
    s->data = e;
    s->next = NULL;
    (*Q).rear->next = s;
    (*Q).rear = s;
    return OK;
}

Status DeQueue_L(LinkQueue *Q)
{
    QNode *q = (*Q).front->next;
    (*Q).front->next = q->next;
    if (q->next == NULL)
        (*Q).rear = (*Q).front;
    free(q);
    return OK;
}

//创建二叉树: 先序扩展序列 + 递归法
void CreateBiTree(BiTree *T)
{
    char input;
    scanf("%c",&input); //输入数据
    if(input == '#')    //'#'是空节点
    {
       *T = NULL;
    }
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(*T == NULL)
        {
            printf("\n分配动态内存时出错.\n");
            exit(1);
        }
        (*T)->data=input;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
}

void PreOrder(BiTree T) //先序遍历
{
    if(T != NULL)
    {
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
void InOrder(BiTree T) //中序遍历
{
    if(T != NULL)
    {
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T) //后序遍历
{
    if(T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}

void LevelOrder(BiTree T) //层序遍历
{
    LinkQueue Q;
    BiTree p = T;
    if(p == NULL)
    {
        return;
    }
    InitQueue_L(&Q);
    EnQueue_L(&Q, p);
    while( !QueueEmpty_L(Q) )
    {
        p = Q.front->next->data;
        DeQueue_L(&Q);
        printf("%c",p->data);
        if(p->lchild != NULL)
        {
            EnQueue_L(&Q, p->lchild);
        }
        if(p->rchild != NULL)
        {
            EnQueue_L(&Q, p->rchild);
        }
    }
}

int main()
{
    BiTree T;
    CreateBiTree(&T);
    printf("先序遍历序列: ");
    PreOrder(T);
    printf("\n");
    printf("中序遍历序列: ");
    InOrder(T);
    printf("\n");
    printf("后序遍历序列: ");
    PostOrder(T);
    printf("\n");
    printf("层次遍历序列: ");
    LevelOrder(T);
    printf("\n");
    return 0;
}