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

谁践踏了优雅 2024-02-18 22:31 61阅读 0赞

*  [Logout][]

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

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

Input

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

Output

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

Sample Input

9 
    ABDFGHIEC
    FDHGIBEAC

Sample Output

Hint

Source

xam

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        char data;
        struct node *lc;
        struct node *rc;
    };
    char a[101], b[101];
    struct node *creat(char a[], char b[], int n)
    {
        struct node *root;
        if(n == 0)
        {
            return NULL;
        }
        int i;
        root = (struct node *)malloc(sizeof(struct node));
        root->data = a[0];
        for(i = 0; i < n; i++)
        {
            if(b[i] == a[0])
            {
                break;
            }
        }
        root->lc = creat(a+1,b,i);
        root->rc = creat(a+1+i, b+1+i, n - 1- i);
        return root;
    }
    int deep(struct node *root)
    {
        int d, d1, d2;
        if(root != NULL)
        {
            d1 = deep(root->lc);
            d2 = deep(root->rc);
            if(d1 >= d2)
            {
                d = d1 + 1;
            }
            else
            {
                d = d2 + 1;
            }
        }
        else
        {
            d = 0;
        }
        return d;
    }
    int main()
    {
        int n, h;
        while(scanf("%d", &n) != EOF)
        {
            struct node *root;
            scanf("%s %s", a, b);
            root = creat(a,b,n);
            h = deep(root);
            printf("%d\n", h);
        }
        return 0;
    }

[Logout]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Login/logout
[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2562/pid/3343.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2562/pid/3343.html