二叉树的建立与存储，以及遍历方法

梦里梦外; 2022-06-12 11:25 127阅读 0赞

案例输入（其中的“\#”表示空，并且输入过程中不要加回车)  
/\*  
输入序列ABC\#\#DE\#G\#\#F\#\#\#  
输入序列ABD\#\#E\#\#CF\#G\#\#\#  
输入序列ABD\#\#\#C\#\#

\*/

#include <stdio.h> //测试通过，可以运行
    #include <string.h>
    #include <malloc.h>
    #define NULL 0
    
    typedef struct BiTNode      //定义数据结构
    {
        char data;
        struct BiTNode *Lchild;
        struct BiTNode *Rchild;
    } BiTNode,*BiTree;
    
    BiTree Create(BiTree T)   //建立二叉树（先序）
    {
        char ch;
        ch=getchar();
        if(ch=='#')
            T = NULL;
        else
        {
            if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
                printf("Error!");
            T->data=ch;
            T->Lchild = Create(T->Lchild);
            T->Rchild = Create(T->Rchild);
        }
        return T;
    }
    
    void visitNode(BiTree N)
    {
        printf("%c",N->data);
    }
    
    void Pre_order(BiTree T)    //先序遍历二叉树
    {
        if(T != NULL){
            visitNode(T);
            Pre_order(T->Lchild);
            Pre_order(T->Rchild);
        }
    }
    
    void In_order(BiTree T) //中序遍历二叉树
    {
        if(T != NULL){
            In_order(T->Lchild);
            visitNode(T);
            In_order(T->Rchild);
        }
    }
    
    void Post_order(BiTree T)   //后序遍历二叉树
    {
        if(T != NULL){
            Post_order(T->Lchild);
            Post_order(T->Rchild);
            visitNode(T);
        }
    }
    
    int Sum_leafs(BiTree T) //求二叉树叶子（最底端）个数
    {           //可以通过 输入的序列，检验正确与否
        int sum=0,m,n;
        if(T != NULL){
            if( (!T->Lchild) && (!T->Rchild) )
                sum++;  //其实，只有这个位置 ，sum 值有变化。 深入到最底部的时候，这个 sum 就是本次调用的返回值
            m = Sum_leafs(T->Lchild); //肯定会递归的找到 最后一个
            sum+=m;
            n = Sum_leafs(T->Rchild);
            sum+=n;
        }
        return sum;
    }
    /*
    二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。
    深度是指所有结点中最深的结点所在的层数。
    */
    int Depth_of_tree(BiTree T)   //求二叉树的深度
    {
        int dep=0,depl,depr;
        if(T == NULL)
            dep=0;
        else  //有根节点，则深度至少是 1
        {
            depl = Depth_of_tree(T->Lchild);
            depr = Depth_of_tree(T->Rchild);
            dep  = 1 + (depl>depr?depl:depr);   //深度，是最深的那一条枝
        }
        return dep;
    }
    
    int main()
    {
    
        int sum,dep;
        BiTree T=Create(T);
    
        printf("二叉树的 先序遍历 顺序为： \n");
        Pre_order(T);
        printf("\n");
    
        printf("二叉树的 中序遍历 顺序为： \n");
        In_order(T);
        printf("\n");
    
        printf("二叉树的 后序遍历 顺序为： \n");
        Post_order(T);
        printf("\n");
    
        printf("二叉树的叶子（最底端）个数是 ：  ");
        sum=Sum_leafs(T);
        printf("%d\n",sum);
        printf("二叉树的深度是 ：  ");
        dep=Depth_of_tree(T);
        printf("%d\n",dep);
        return 0;
    }