1、树的基本功能的实现（包括桉树状打印二叉树）

关于树的创建可以看看我的另外一篇，可别小看了树的创建，你要是真的把树的创建真真切切的弄懂啦，
那么树后面就好学了很多，否则，很痛苦的；
附链接：https://blog.csdn.net/qq_50504109/article/details/119721763

/**
 * 时隔一百年总算学到树啦
 * 不容易
 *
 * 测试用例：AB..CD... 或者 AB.DF..G..C.E.H..
 */

#include<stdio.h>
#include <mm_malloc.h>
typedef struct{
    char data;
    struct BiNode *LChild;
    struct BiNode *RChild;


}BiTNode,*BiTree;
int count = 0;
int depth = 0;
int main(){
    void PreCreateBiTree(BiTree *T);
    void InCreateBiTree(BiTree *T);
    void PostCreateBiTree(BiTree *T);
    void PreOrder(BiTree T);
    void InOrder(BiTree T);
    void PostOrder(BiTree T);
    void PreOrderLeaves(BiTree T);
    void PostOrderAmountLeaves(BiTree T);
    int DCPostOrderAmountLeaves(BiTree T);
    int PostTreeDepth(BiTree T);
    void PreTreeDepth(BiTree T,int h);
    void PrintTree(BiTree T,int nLayer);

    BiTree T ;
    //先序创建树
    PreCreateBiTree(&T);

    printf("先序遍历序列为:");
    PreOrder(T);
    printf("\n中序遍历序列为:");
    InOrder(T);
    printf("\n后序遍历序列为:");
    PostOrder(T);
    printf("\n输出叶子结点:");
    PreOrderLeaves(T);

    printf("\n使用全局变量后序统计叶子结点的数目");
    PostOrderAmountLeaves(T);
    printf("\n叶子结点的个数为:%d",count);

    printf("\n使用分治后序统计叶子结点的数目");
    int leafCount = DCPostOrderAmountLeaves(T);
    printf("\n叶子结点的个数为:%d",leafCount);

    int depth1 = PostTreeDepth(T);
    printf("\n树的高度:%d",depth1);

    PreTreeDepth(T,1);
    printf("\n树的高度:%d",depth);

    printf("\n桉树状打印二叉树:\n");
    PrintTree(T,1);

}

//先序创建二叉树
void PreCreateBiTree(BiTree *T){//这里必须要用二级指针，不用你操作的结果根本拿不到，你可以先用一级指针思考一下，你就会发现真的很妙，

      char ch;
      ch = getchar();
          if (ch != '.'){
              *T = (BiTNode *)malloc(sizeof(BiTNode));
              (*T)->data = ch;
              PreCreateBiTree(&((*T)->LChild));//这个地方要传地址而不是temp->LChild，temp->LChild是等于NULL的，你要给这个变量的地址才行
              PreCreateBiTree(&((*T)->RChild));
          }else{
              *T = NULL;
          }
      }
//中序创建二叉树
void InCreateBiTree(BiTree *T){//这里必须要用二级指针，不用你操作的结果根本拿不到，你可以先用一级指针思考一下，你就会发现真的很妙，

    char ch;
    ch = getchar();
    if (ch != '.'){
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        InCreateBiTree(&((*T)->LChild));//这个地方要传地址而不是temp->LChild，temp->LChild是等于NULL的，你要给这个变量的地址才行
        (*T)->data = ch;
        InCreateBiTree(&((*T)->RChild));
    }else{
        *T = NULL;
    }
}
//后序创建二叉树
void PostCreateBiTree(BiTree *T){//这里必须要用二级指针，不用你操作的结果根本拿不到，你可以先用一级指针思考一下，你就会发现真的很妙，

    char ch;
    ch = getchar();
    if (ch != '.'){
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        PostCreateBiTree(&((*T)->LChild));//这个地方要传地址而不是temp->LChild，temp->LChild是等于NULL的，你要给这个变量的地址才行
        PostCreateBiTree(&((*T)->RChild));
        (*T)->data = ch;
    }else{
        *T = NULL;
    }
}

//先序遍历二叉树
void PreOrder(BiTree T){
    if ( T != NULL){
        printf("%c",T->data);
        PreOrder(T->LChild);
        PreOrder(T->RChild);
    }
}
//中序遍历
void InOrder(BiTree T){
    if ( T != NULL){
        InOrder(T->LChild);
        printf("%c",T->data);
        InOrder(T->RChild);
    }
}
//后序遍历
void PostOrder(BiTree T){
    if ( T != NULL){

        PostOrder(T->LChild);
        PostOrder(T->RChild);
        printf("%c",T->data);
    }
}

//先序输出二叉树中的叶子结点  其实也就是遍历(有条件的输出)，只不过这次遍历在输出的时候有条件而已，那就是当前节点的左孩子和右孩子都必须是空才输出，
void PreOrderLeaves(BiTree T) {

    if (T!=NULL){

        if ( T->LChild == NULL && T->RChild == NULL){
             printf("%c",T->data);
        }
        PreOrderLeaves(T->LChild);
        PreOrderLeaves(T->RChild);
    }
}
//后序遍历统计叶子结点的数目，跟上面一样的
void PostOrderAmountLeaves(BiTree T){

    if (T != NULL){
          PostOrderAmountLeaves(T->LChild);
          PostOrderAmountLeaves(T->RChild);
        if (T->LChild == NULL && T->RChild == NULL){
            count++;//用一个全局变量就够了
        }

    }

}
//采用分治后序遍历统计叶子结点的数目，这种方法必须是后序，因为最终的结果是要返回到根节点的，而且入口也是根节点，只有后序符合
// 遇到空节点返回0，遇到节点返回1，否则，就是该节点的叶子数，就是他的左分支加上右分支递归遍历就可
int DCPostOrderAmountLeaves(BiTree T){
     int LeafCount = 0;
    if (T == NULL){
        LeafCount = 0;
    }else if (T->LChild == NULL && T->RChild == NULL){
          LeafCount = 1;
    }else{
         LeafCount = DCPostOrderAmountLeaves(T->LChild)+DCPostOrderAmountLeaves(T->RChild);
    }
    return LeafCount;
}

//递归后序遍历得到数的高度       思路就是：不停的递归比较左右分支，谁的深度大，就返回那个分支的值
int PostTreeDepth(BiTree T){

     int hl,hr,max;
    if (T != NULL){
        hl = PostTreeDepth(T->LChild);
        hr = PostTreeDepth(T->RChild);
        max = hl>hr?hl:hr;
        return (max+1);//我们求的是当前节点左右分支的高度，还没有加上本身，所以要加1；
    }else{
        return 0;
    }
}
//递归前序遍历得到树的高度 这个没那么容易想到，看书的
void PreTreeDepth(BiTree T,int h){//h的初始值传入1，depth的初始值为0是全局变量

    if ( T != NULL){

        if (h > depth){
            depth = h;
        }
        PreTreeDepth(T->LChild,h+1);
        PreTreeDepth(T->RChild,h+1);

    }

}

//桉树状打印二叉树
void PrintTree(BiTree T,int nLayer){
 /**
  *   根据输出的结果来看，在控制台输出肯定是自上而下，但是你会发现前序中序后序都没有你要的结果，但是逆中序却有你想要的结果
  *   因此，我们输出的时候要时候逆中序，但是空格，怎么办的，你会发现他们所在的层次就是他们的每行前面的空格数，因此，我们需要用一个变量记录着层数
  *   然后，先把空格数输出之后，在输出字符并换行
  */
    if (T == NULL){
        return;
    }
    PrintTree(T->RChild,nLayer+1);
    for (int i = 0; i < nLayer; ++i) {
          printf(" ");
    }
    printf("%c\n",T->data);
    PrintTree(T->LChild,nLayer+1);


}