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

不念不忘少年蓝@ 2022-07-12 07:28 152阅读 0赞

Problem Description

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

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

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

9  
ABDFGHIEC  
FDHGIBEAC  
Example Output

5  
Hint

Author

xam

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    char a[55];
    char b[55];
    struct node
    {
        int data;
        struct node *l, *r;
    };
    struct node *creat(int n, char *a, char *b)
    {
        int i;
        if(n == 0) return NULL;
        struct node *root;
        root = (struct node *) malloc (sizeof(struct node));
        root -> data = a[0];
        for(i = 0; i < n; i++)
        {
            if(b[i] == a[0])
                break;
        }
        root -> l = creat(i, a+1, b);
        root -> r = creat(n-1-i, a+1+i, b+1+i);
        return root;
    };
    int high(struct node *root)
    {
        int d1, d2;
        if(root)
        {
            d1 = high(root -> l);
            d2 = high(root -> r);
            return d1 > d2? d1+1 : d2+1;
        }
        else
            return 0;
    }
    int main()
    {
        int t, n;
        while(~scanf("%d", &t))
        {
            scanf("%s%s", a, b);
            struct node *root;
            n = strlen(a);
            root = creat(n, a, b);
            printf("%d\n", high(root));
        }
        return 0;
    }