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

水深无声 2022-12-21 04:57 113阅读 0赞

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

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

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

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

Sample  
Input  
9  
ABDFGHIEC  
FDHGIBEAC  
Output  
5

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
        char data;
        struct node *left;
        struct node *right;
    };
    char a[150],b[150];
    struct node *creat(char a[],char b[],int n)//建树
    {
        
        struct node *root;
        int i;
        if(n==0)
        {
        
           return NULL;
        }
        root=(struct node *)malloc(sizeof(struct node));
        root->data=a[0];
        for(i=0;i<n;i++)
        {
        
            if(b[i]==a[0])
                break;
        }
        root->left=creat(a+1,b,i);//递归建左子树
        root->right=creat(a+1+i,b+1+i,n-1-i);//递归建右子树
        return root;
    };
    int deep(struct node *root)//深度计算
    {
        
        int d,dl,dr;
        if(root)
        {
        
            dl=deep(root->left);//递归左子树深度
            dr=deep(root->right);//递归右子树深度
            if(dl>=dr)
                d=dl+1;
            else
                d=dr+1;
        }
        else
        {
        
            d=0;
        }
            return d;
    }
    int main()
    {
        
        int h,n;
        while(~scanf("%d",&n))
        {
        
            struct node *root;
            scanf("%s %s",a,b);
            root=creat(a,b,n);
            h=deep(root);
            printf("%d\n",h);
        }
    }

[思路来源][Link 1]

[Link 1]: https://blog.csdn.net/weixin_44015865/article/details/102788763