博客

新手，摸索着前进…….

由先序序列和中序序列可以唯一确定一棵二叉树，算法实现步骤如下：

1）根据先序序列确定树的根结点

2）根据根结点在中序序列中的位置划分出二叉树的左右子树包含哪些结点。

然后根据左、右字数结点在先序序列中的次序可以确定子树的根结点，即回到步骤 1）。

如此重复上述步骤，直到每棵子树仅有一个结点（该子树的根结点）为止。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OVERFLOW 0
typedef struct Node
{
    char data;
    struct Node *lchild,*rchild;
    //Node(){data = 0;lchild = rchild = NULL;}
}Node,*BiTree;

char PreString[30],InString[30];//先序和中序遍历字符串

BiTree Build(char *PreString,char *InString,int s1,int e1,int s2,int e2)
{
//    BiTree T = (BiTree)malloc(sizeof(Node));
//    if(T == NULL)
//    {
//        exit(OVERFLOW);
//    }
    BiTree T = new Node();
    T -> data = PreString[s1];
    int rootIdx;//根结点所在序号
    for(int i = s2;i <= e2;i++)
    {
        if(PreString[s1] == InString[i])
        {
            rootIdx = i;
            break;
        }
    }
    int llen = rootIdx - s2;
    int rlen = e2 - rootIdx;
    if(llen != 0)
    {
        T -> lchild = new Node();
        T -> lchild = Build(PreString,InString,s1 + 1,s1 + llen,s2,s2 + llen - 1);
    }
    else
        T -> lchild = NULL;
    if(rlen != 0)
    {
        T -> rchild = new Node();
        T -> rchild = Build(PreString,InString,e1 - rlen + 1,e1,e2 - rlen + 1,e2);
    }
    else
    {
        T -> rchild = NULL;
    }
    return T;
}

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

int main()
{
    printf("请输入先序遍历字符串：");
    scanf("%s",PreString);
    printf("请输入中序遍历字符串：");
    scanf("%s",InString);
    BiTree T = NULL;
    T = Build(PreString,InString,0,strlen(PreString)-1,0,strlen(InString)-1);
    printf("此二叉树的后序遍历为：");
    PostOrder(T);
    printf("\n");
    return 0;
}