Question

关于二叉树遍历的问题

关于二叉树遍历的问题一个二叉树按先序遍历的结点序列为52143687IKJ（每个字符为一个结点值）,
中序序列为12345678IJK, 那么这棵树
的后序序列是什么？

Answer 1

根据先序序列52143687IKJ,得知5是根结点.
根据中序序列12345678IJK,得知1234是根结点5的左子树,678IJK是根结点5的右子树.
画出二叉树:

       5
      / \
     2   6
    / \   \
   1   4   8
      /   / \
     3   7   I
              \
               K
              /
             J

后序序列是13427JKI865


//C语言测试程序

#include "stdio.h"
#include "stdlib.h"
struct tree
{
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree treenode;
typedef treenode *btree;

btree createbtree(char *data,int pos,int maxPos) //递归创建法
{
    btree newnode;

    if(data[pos]==0 || pos>maxPos)
    {
        return NULL;
    }
    else
    {
        newnode=(btree)malloc(sizeof(treenode));
        newnode->data=data[pos];
        newnode->left=createbtree(data,2*pos,maxPos);
        newnode->right=createbtree(data,2*pos+1,maxPos);
        return newnode;
    }
}

void inorder(btree ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%C ",ptr->data);
        inorder(ptr->right);
    }
}

void preorder(btree ptr)
{
    if(ptr!=NULL)
    {
        printf("%C ",ptr->data);
        preorder(ptr->left);
        preorder(ptr->right);
    }
}

void postorder(btree ptr)
{
    if(ptr!=NULL)
    {
        postorder(ptr->left);
        postorder(ptr->right);
        printf("%C ",ptr->data);
    }
}

int main()
{
    btree root=NULL;
    int i;

    char data[64]={0,'5','2','6','1','4',0,'8',
                   0,0,'3',0,0,0,'7','I',
                   0,0,0,0,0,0,0,0,
                   0,0,0,0,0,0,0,'K',
                   0,0,0,0,0,0,0,0,
                   0,0,0,0,0,0,0,0,
                   0,0,0,0,0,0,0,0,
                   0,0,0,0,0,0,'J',0};
    root=createbtree(data,1,63);
    printf("二叉树的顺序存储内容: ");
    for(i=1;i<64;i++)
    {
        if(data[i]==0)
        {
            printf("^ ");
        }
        else
        {
            printf("%c ",data[i]);
        }
    }

    printf("\n二叉树的先序遍历序列: ");
    preorder(root);
    printf("\n二叉树的中序遍历序列: ");
    inorder(root);
    printf("\n二叉树的后序遍历序列: ");
    postorder(root);

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