Question

二叉树的中序和前序

Answer 1

二叉树的前序序列是ABDEGHCFIJ  中序序列为DBGEHACIFJ

根据前序序列ABDEGHCFIJ, 可以确定A是根结点.

中序序列DBGEH A CIFJ里以A为中心, DBGEH是A的左子树, CIFJ是A的右子树.

          A
         / \
    DBGEH   CIFJ

前序序列ABDEGHCFIJ里B紧跟A之后, B是A的左孩子.
中序序列DBGEHACIFJ里D排在最前, D之后是B, 预计D没有左子树,也没有右子树,
并且D是B的左孩子.

          A
         / \
        B   CIFJ
       / \
      D   GEH

前序序列ABDEGHCFIJ里E跟在B后面, 预计E是B的右孩子.
中序序列DBGEHACIFJ里E的左边是G, 而右边是H, 预计E的左孩子是G, 右孩子是H,
再次观察前序序列ABDEGHCFIJ里的EGH这种顺序可以确定,E的左右孩子就是G和H.

          A
         / \
        B   CIFJ
       / \
      D   E
         / \
        G   H

前序序列ABDEGHCFIJ里的CFIJ, C排在最前,
中序序列DBGEHACIFJ里的C在A的后面, 可以确定C是A的右孩子.

          A
         / \
        B   C
       / \   \
      D   E   IFJ
         / \
        G   H

前序序列ABDEGHCFIJ里F跟在C的后面, F会是C的左孩子或者右孩子,
而F后面跟着的是IJ, 预计I和J属于F的子树.
中序序列DBGEHACIFJ里C之后是F, 而F的左边是I, 右边是J, I跟在C的后面,
可以确定F是C的右孩子, I和J是F的左右孩子.

二叉树示意图:
           A
         /    \
        B      C
       / \      \
      D   E      F
         / \    / \
        G   H  I   J

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


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

创建二叉树,输入前序扩展序列: ABD##EG##H##C#FI##J##
前序遍历序列: A B D E G H C F I J
中序遍历序列: D B G E H A C I F J
后序遍历序列: D G H E B I J F C A


#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;
}