前序中序，中序后序建立二叉树及二叉树的深度

桃扇骨 2022-04-22 02:16 171阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    struct tree
    {
        char data;
        tree *l,*r;
    };
    char a[55],b[55];//a前序b中序
    int l1,h1,l2,h2;
    tree *creat() //前序建立
    {
        tree *root;
        char c;
        c = a[l1++];
        if(c == ',')
            return NULL;
        else
        {
            root = new tree;
            root->data = c;
            root->l=creat();
            root->r=creat();
        }
        return root;
    }
    tree *creat2(int n,char a[],char b[])//前序中序建立
    {
        tree *root;
        int i;
        if(n == 0)
            return NULL;
        root = new tree;
        root->data=a[0];
        for(i = 0;i < n;i++)
        {
            if(b[i] == a[0])
                break;
        }
        root->l=creat2(i,a+1,b);
        root->r=creat2(n-i-1,a+i+1,b+i+1);
    
        return root;
    }
    tree *creat3(int n,char a[],char b[])//中序后序建立
    {
        tree *root;
        int i;
        if(n == 0)
            return NULL;
        root = new tree;
        root->data=b[n-1];
        for(i = 0;i < n;i++)
        {
            if(a[i] == b[n-1])
                break;
        }
        root->l=creat3(i,a,b);
        root->r=creat3(n-i-1,a+i+1,b+i);
        return root;
    }
    void preorder(tree *root) //前序遍历
    {
        tree *p;
        p = root;
        if(p!=NULL)
        {
            printf("%c",p->data);
            preorder(p->l);
            preorder(p->r);
        }
    }
    void inorder(tree *root)//中序遍历
    {
       tree *p;
        p = root;
        if(p!=NULL)
        {
            inorder(p->l);
            printf("%c",p->data);
            inorder(p->r);
        }
    }
    void postorder(tree *root)//后序遍历
    {
        tree *p;
        p = root;
        if(p!=NULL)
        {
            postorder(p->l);
            postorder(p->r);
            printf("%c",p->data);
        }
    }
    int treehight(tree *t) //二叉数高度
    {
       if(!t)
        return 0;
       else
        return treehight(t->l)>treehight(t->r)?treehight(t->l)+1:treehight(t->r)+1;
    }
    int main()
    {
        int n,t;
        scanf("%d",&t);
        while(t--)
        {
            tree *root;
            scanf("%s%s",a,b);
            n = strlen(a);
            root = creat3(n,a,b);
            printf("%d\n",treehight(root));
        }
        return 0;
    }