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

缺乏、安全感 2022-06-04 23:26 146阅读 0赞

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

#include<iostream>
    #include <malloc.h>
    #include<string.h>
    using namespace std;
    struct node
    {
        char data;
        struct node  *rchild,*lchild;
    }tree;
    struct node *creat(char *a1,char*a2,int n)
    {
        struct node *root;
        if(n<=0) return NULL;
        else
        {
            root=(struct node *)malloc(sizeof(struct node ));
            root->data=a2[n-1];
            //将后序遍历的最后一个节点当作当前子树的根
            /*        指针形式
            char *a;
            for (a=a1;a!=NULL;a++)
        {
                if(*a==a2[n-1])
                    break;
            }
            int lchildroot=a-a1;//左子树的长度
            root->lchild=creat(a1,a2,lchildroot);
            root->rchild=creat(a1+1+lchildroot,a2+lchildroot,n-lchildroot-1);
            */
            int i;                   //数组形式
            for ( i=0;i<n;i++)
            {
                if(a1[i]==a2[n-1])
                    break;
            }
            int lchildroot=i;//左子树的长度
            root->lchild=creat(a1,a2,lchildroot);
            root->rchild=creat(a1+1+lchildroot,a2+lchildroot,n-lchildroot-1);
        }
      return root;
    };
    int deep(struct node *root)
    {
        int d=0;
        if(root)
        {
            int l=deep(root->lchild);
            int r=deep(root->rchild);
            d=l>r?l+1:r+1;
        }
        return d;
    }
    int main()
    {
        int n,x;
        cin>>x;
        while(x--)
        {
    
            char a1[55],a2[55];
            struct node *root;
            cin>>a1>>a2;
            n=strlen(a1);
            root=creat(a1,a2,n);
            cout<<deep(root)<<endl;
    
        }
    }

[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2227/pid/2804