二叉树

╰半橙微兮° 2024-02-18 22:31 7阅读 0赞

二叉树所有相关的知识

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    struct node
    {
        char data;
        struct bitree *l,*r;
    };
    char a[55],b[55];//a前序b中序
    int l1,h1,l2,h2;
    struct node *creat() //前序建立
    {
        struct node *root;
        char c;
        c = a[l1++];
        if(c == ',')
            return NULL;
        else
        {
            root = (struct node *)malloc(sizeof(struct node));
            root->data = c;
            root->l=creat();
            root->r=creat();
        }
        return root;
    }
    struct node *creat2(int n,char *a,char *b)//前序中序建立
    {
        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->l=creat2(i,a+1,b);
        root->r=creat2(n-i-1,a+i+1,b+i+1);
    
        return root;
    }
    struct node *creat3(int n,char *a,char *b)//中序后序建立
    {
        struct node *root;
        int i;
        if(n == 0)
            return NULL;
        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->l=creat3(i,a,b);
        root->r=creat3(n-i-1,a+i+1,b+i);
        return root;
    }
    void preorder(struct node *root) //前序遍历
    {
        struct node *p;
        p = root;
        if(p!=NULL)
        {
            printf("%c",p->data);
            preorder(p->l);
            preorder(p->r);
        }
    }
    void inorder(struct node *root)//中序遍历
    {
        struct node *p;
        p = root;
        if(p!=NULL)
        {
            inorder(p->l);
            printf("%c",p->data);
            inorder(p->r);
        }
    }
    void postorder(struct node *root)//后序遍历
    {
        struct node *p;
        p = root;
        if(p!=NULL)
        {
            postorder(p->l);
            postorder(p->r);
            printf("%c",p->data);
        }
    }
    int treehight(struct node *t) //二叉数高度
    {
        int h,lh,rh;
        if(t == NULL)
        {
            h = 0;
        }
        else
        {
            lh = treehight(t->l);
            rh = treehight(t->r);
            if(lh>rh)
                h = lh+1;
            else
                h = rh+1;
        }
        return h;
    }
    int main()
    {
        int n,t;
        scanf("%d",&t);
        while(t--)
        {
            struct node *root;
            scanf("%s%s",a,b);
            n = strlen(a);
            root = creat3(n,a,b);
            printf("%d\n",treehight(root));
        }
        return 0;
    }