二叉树的基本操作

悠悠 2022-05-18 07:19 215阅读 0赞

#include<stdio.h>
    #include<malloc.h>
    
    struct node{
        struct node *lc,*rc;
        int data;
    
    };
    
    //创建二叉排序树
    struct node *create_sort_tree(struct node *root,int x){
    
        if(root==NULL){
            printf("直接插入\n");
            root=(struct node *)malloc(sizeof(struct node));
            root->data=x;
            root->lc=NULL;
            root->rc=NULL;
            printf("root->data %d\n",root->data);
            return root;
        }else{
            if(root->data>x){
                printf("向左插入\n");
                root->lc=create_sort_tree(root->lc,x);
            }else if(root->data<x){
                printf("向右插入\n");
                root->rc=create_sort_tree(root->rc,x);
            }else{
                printf("The node has been created last time!");
            }
            printf("ROOT->DATA %d\n",root->data);
            return root;
        }
    }
    
    //先序遍历二叉树
    void First_put(struct node *root){
        if(root!=NULL){
            printf("%d ",root->data);
            First_put(root->lc);
            First_put(root->rc);
        }
    
    }
    
    //中序遍历二叉树
    void Mid_put(struct node *root){
        if(root!=NULL){
            Mid_put(root->lc);
            printf("%d ",root->data);
            Mid_put(root->rc);
        }
    }
    
    
    //后序遍历二叉树
    void Last_put(struct node *root){
        if(root!=NULL){
            Last_put(root->lc);
            Last_put(root->rc);
        }
    }
    
    //层次遍历二叉树
    void Level_put(struct node *root){
        struct node *temp[100];//用一个指针类型的结构体数组存节点
        int i,j;
        i=j=-1;
        int num=0;//记录叶子节点个数
        if(root!=NULL){
            temp[++i]=root;
        }
        while(j<i){//边界条件   当j>=i时表示树中所有节点均遍历完成
            ++j;
            //左右孩子不为空分别入队
            if(temp[j]->lc!=NULL){
                temp[++i]=temp[j]->lc;
            }
            if(temp[j]->rc!=NULL){
                temp[++i]=temp[j]->rc;
            }
            //左右孩子节点为空则为叶子节点
            if(temp[j]->lc==NULL&&temp[j]->rc==NULL){
                printf("叶子:%d\n",temp[j]->data);
                num++;
            }
        }
        printf("叶子节点的个数是 %d\n",num);
        for(int x=0;x<=i;x++){
            printf("%d ",temp[x]->data);
        }
    }
    
    //求二叉树深度
    int Tree_deepth(struct node *root){
        int lh,rh;
        if(root==NULL){
            return 0;
        }else{
            lh=Tree_deepth(root->lc);
            rh=Tree_deepth(root->rc);
            if(lh>rh){
                return lh+1;
            }else{
                return rh+1;
            }
        }
    
    }
    
    //入口函数
    int main(){
        int a[100];
        struct node *root;
        root=NULL;
        for(int i=0;i<8;i++){
            scanf("%d",&a[i]);
            root=create_sort_tree(root,a[i]);
        }
        int high=Tree_deepth(root);
        printf("树的高度是:%d\n",high);
        return 0;
    
    }