SDUTACM 数据结构实验之二叉树四：还原二叉树

骑猪看日落 2022-07-15 00:18 153阅读 0赞

#### Problem Description ####

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

#### Input ####

输入数据有多组，每组数据第一行输入 1 个正整数 N(1 <= N <= 50) 为树中结点总数，随后 2 行先后给出先序和中序遍历序列，均是长度为 N 的不包含重复英文字母 ( 区分大小写 ) 的字符串。

#### Output ####

输出一个整数，即该二叉树的高度。

#### Example Input ####

9 
    ABDFGHIEC
    FDHGIBEAC

#### Example Output ####

#### Hint ####

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct hh
    {
        char data;
        struct hh *l;
        struct hh *r;
    };
    struct hh *creat(char *pre,char *in,int n)
    {
        char *p;
        struct hh *s;
        int k;
        if(n<=0)
            return NULL;
        s=(struct hh *)malloc(sizeof(struct hh));
        s->data=*pre;
        for(p=in;p<in+n;p++)
            if(*p==*pre)
            break;
        k=p-in;
        s->l=creat(pre+1,in,k);
        s->r=creat(pre+1+k,p+1,n-k-1);
        return s;
    };
    int deep(struct hh *p)
    {
        int ld,rd;
        if(p==NULL)
            return 0;
        else
        {
            ld=deep(p->l);
            rd=deep(p->r);
            if(ld>rd)
                return ld+1;
            else
                return rd+1;
        }
    }
    int main()
    {
        struct hh *p;
        int n;
        char pre[100],in[100];
        while(scanf("%d",&n)!=EOF)
        {
            scanf("%s",&pre);
            scanf("%s",&in);
            p=creat(pre,in,n);
            printf("%d\n",deep(p));
        }
        return 0;
    }