数据结构之二叉树基础（C语言）

待我称王封你为后i 2022-04-03 07:28 240阅读 0赞

树：(Tree)

性质：  
子树是不相交的  
除了根节点之外，每个节点有且仅有一个节结点  
一颗N个结点的树有N-1条边  
概念：  
结点的度：结点的子树个数  
树的度：树的所有结点中最大的度数  
叶结点：度为0的结点  
结点的层次：规定根节点在1层，其他任意节点的层数是其父节点的层数加1  
树的深度：树中所有结点中最大层次是这棵树的深度

二叉树：（每个结点至多有2颗子树）  
种类：完全二叉树，满二叉树  
几个重要性质：  
1，在二叉树的第i层上至多有2的(i-1)次方 个结点  
2，深度为k的二叉树至多有2的k次方-1个结点(k>=1)  
3，对任何一颗二叉树T,如果其终端结点树为n0，度为2的结点数为n2，则n0 = n2 + 1。（推导略 见课本124页）  
树的遍历：  
先序遍历，中序遍历，后序遍历，层次遍历

代码如下：

/*
        数据结构之二叉树
        实现函数：
        创建，遍历（先，中，后，层序），求树的深度；求叶子数
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int ElemType;
    typedef int Status;
    typedef struct Tree{
        ElemType data;
        struct Tree *lchild;
        struct Tree *rchild;
    }Tree,*BinTree;
    //创建二叉树
    Status CreateBinTree(BinTree &T){
        int tmp;
        scanf("%d",&tmp);
        if(tmp == 0){
            T = NULL;
        }
        else{
            T = (BinTree)malloc(sizeof(Tree));
            if(!T)
                exit(OVERFLOW);
            T->data = tmp;
            //printf("data:%d\n",tmp);
            CreateBinTree(T->lchild);
            CreateBinTree(T->rchild);
        }
        return OK;
    }
    //先序遍历
    void PreTraversalBinTree(BinTree &T){
        //递归循环输出
        if(T){
            printf("%d ",T->data);
            PreTraversalBinTree(T->lchild);
            PreTraversalBinTree(T->rchild);
        }
    }
    //中序遍历
    void MidTraversalBinTree(BinTree &T){
        if(T){
            MidTraversalBinTree(T->lchild);
            printf("%d ",T->data);
            MidTraversalBinTree(T->rchild);
        }
    }
    //后序遍历
    void PostTraversalBinTree(BinTree &T){
        if(T){
            PostTraversalBinTree(T->lchild);
            PostTraversalBinTree(T->rchild);
            printf("%d ",T->data);
        }
    }
    //层序遍历
    void LevelTravresalBiTree(BinTree &T){
        if(T == NULL)
            return;
        BinTree p[101];
        int index = 0,num_put = 0;
        p[index++] = T;
        while(num_put < index){
            BinTree q = p[num_put++];
            printf("%d ",q->data);
            if(q->lchild != NULL){
                p[index++] = q->lchild;
            }
            if(q->rchild != NULL){
                p[index++] = q->rchild;
            }
        }
    }
    //求树的深度
    int DepthOfBinTree(BinTree &T){
        if(T == NULL)
            return 0;
        else{
            int m = DepthOfBinTree(T->lchild) + 1;
            int n = DepthOfBinTree(T->rchild) + 1;
            if(m > n)return m;
            else
                return n;
        }
    }
    //求叶子的个数
    int SumOfBinTreeLeaf(BinTree &T){
        if(!T){
            return 0;
        }
        if(!T->lchild && !T->rchild)
            return 1;
        else{
            return SumOfBinTreeLeaf(T->lchild) + SumOfBinTreeLeaf(T->rchild);
        }
    }
    //测试用例
    int main(){
        BinTree T;
        CreateBinTree(T);
        printf("层序遍历结果为：\n");
        LevelTravresalBiTree(T);
        printf("\n先序遍历结果为：\n");
        PreTraversalBinTree(T);
        printf("\n中序遍历结果为：\n");
        MidTraversalBinTree(T);
        printf("\n后序遍历结果为：\n");
        PostTraversalBinTree(T);
        printf("\n树的深度：%d\n",DepthOfBinTree(T));
        DepthOfBinTree(T);
        printf("\n叶子数：%d\n",SumOfBinTreeLeaf(T));
        return 0;
    }