数据结构实验之二叉树八：（中序后序）求二叉树的深度

r囧r小猫 2022-12-21 04:57 108阅读 0赞

## 数据结构实验之二叉树八：（中序后序）求二叉树的深度 ##

Description  
已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。

Input  
输入数据有多组，输入T，代表有T组数据。每组数据包括两个长度小于50的字符串，第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。

Output  
输出二叉树的深度。

Sample  
Input  
2  
dbgeafc  
dgebfca  
lnixu  
linux  
Output  
4  
3

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        
        char data;
        struct node *left;
        struct node *right;
    };
    char a[150],b[150];
    int n;
    struct node *creat(char a[],char b[],int n)//建树
    {
        
        struct node *root;
        int i;
        if(n==0)
        {
        
            root=NULL;
        }
        else
        {
        
            root=(struct node *)malloc(sizeof(struct node));
            root->data=b[n-1];
            for(i=0;i<n;i++)
            {
        
                if(a[i]==b[n-1])
                    break;
            }
            root->left=creat(a,b,i);
            root->right=creat(a+1+i,b+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 t,d;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%s %s",a,b);
            n=strlen(a);
            struct node *root;
            root=creat(a,b,n);
            d=deep(root);
            printf("%d\n",d);
        }
    }