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

约定不等于承诺〃 2022-06-06 12:15 106阅读 0赞

数据结构实验之二叉树八：（中序后序）求二叉树的深度  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

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

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

输出二叉树的深度。  
Example Input

2  
dbgeafc  
dgebfca  
lnixu  
linux  
Example Output

4  
3  
Hint

Author

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    typedef struct node
    {
        char data;
        struct node *lc, *rc;
    } bt, *pbt;
    
    const int MAX = 55;
    
    int getdeep(pbt root)//得到数的深度
    {
        if (root == NULL)
            return 0;
        int dp = 0;
        int dl = getdeep(root->lc);
        int dr = getdeep(root->rc);
        dp = dl > dr ? dl + 1 : dr + 1;
        return dp;
    }
    
    pbt pre_midoriginal(int n, char last[], char mid[])//先序中序还原二叉树
    {
        if (n == 0)
            return NULL;
        char *p;
        for (p = mid; p != '\0'; p++)
        {
            if (*p == last[0])
                break;
        }
        int nn;
        nn = p - mid;
        pbt root = new bt;
        root->data = last[0];
        //后序输出同一个节点先输出右子树再输出左子树
        root->rc = pre_midoriginal(n - nn - 1, last + 1, p + 1);//参数依次是，右子树元素个数，右子树的后续，右子树的中序
        root->lc = pre_midoriginal(nn, last + n - nn, mid);
        return root;
    }
    int main()
    {
        pbt root;
        root = NULL;
        char a[MAX], b[MAX];
        int n;
        char c[MAX];
        cin >> n;
        while (n--)
        {
            cin >> a >> b;
            int len = strlen(a);
            for (int i = 0; i < len; i++)//把后序遍历逆置，便于使用
            {
                c[i] = b[len - i - 1];
            }
            c[len] = '\0';
            root = pre_midoriginal(len, c, a);
            int deep = getdeep(root);
            cout << deep << endl;
        }
        return 0;
    }