C语言数据结构之二叉树数据结构实验之二叉树四：（先序中序）还原二叉树

痛定思痛。 2022-05-31 01:38 139阅读 0赞

数据结构实验之二叉树四：（先序中序）还原二叉树  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

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

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

Output

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

9  
ABDFGHIEC  
FDHGIBEAC  
Example Output

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