二叉树的重建

时间：2010-05-28 来源：buptstehc

题目来源：Tree Recovery
由前序序列可以知道根的位置，再根据根再中序序列中的位置可以得到左右子树。重建时先恢复根，再恢复左子树和右子树，由此可以用递归实现。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLEN 27

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode;

void createBiTree(BiTNode **T, char pre[], char in[])
{
    char l_pre[MAXLEN], l_in[MAXLEN], r_pre[MAXLEN], r_in[MAXLEN];
    char *root;
    int l_len, r_len;

    if(strlen(pre) > 0)
    {
        root = strchr(in, *pre);
        l_len = root - in;
        r_len = strlen(in) - l_len - 1;

        strncpy(l_pre, pre + 1, l_len);
        strncpy(l_in, in, l_len);
        strncpy(r_pre, pre + l_len + 1, r_len);
        strncpy(r_in, in + l_len + 1, r_len);
        l_pre[l_len] = l_in[l_len] = r_pre[r_len] = r_in[r_len] = '\0';

        if((*T = (BiTNode *)malloc(sizeof(BiTNode))) == NULL)
            return;

        (*T)->data = *root;
        createBiTree(&((*T)->lchild), l_pre, l_in);
        createBiTree(&((*T)->rchild), r_pre, r_in);
    }
    else
        *T = NULL;

    return;
}

void SufOrderTraverse(BiTNode *T)
{
    if(T->lchild)
            SufOrderTraverse(T->lchild);
    if(T->rchild)
            SufOrderTraverse(T->rchild);
    printf("%c", T->data);

    return;
}

int main(void)
{
    char pre[MAXLEN], in[MAXLEN];
    BiTNode *T;
    while(scanf("%s %s", pre, in) == 2)
    {
        createBiTree(&T, pre, in);
        SufOrderTraverse(T);
        printf("\n");
    }
    return 0;
}