二叉树的遍历以及求二叉树深度和结点个数_借助二叉树的遍历求二叉树中叶子结点个数-CSDN博客

本文链接：https://blog.csdn.net/FoggyProgrammer/article/details/104058935

程序要求

建立二叉树的二叉链表存储结构，实现二叉树的前序、中序、后序递归遍历
计算二叉树中叶子结点的数目
计算二叉树的深度
求二叉树结点个数

算法分析

遍历二叉树
先序遍历二叉树：
若二叉树为空，则空操作；否则
(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。
中序遍历二叉树：
若二叉树为空，则空操作；否则
(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。
后序遍历二叉树：
若二叉树为空，则空操作；否则
(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。
统计二叉树中叶子结点的个数
在遍历算法中增添一个“计数”的参数，遍历二叉树，在遍历过程中查找叶子结点。若是叶子，则计数参数+1。
求二叉树的深度
(1)二叉树的深度应为其左、右子树深度的最大值+1。
(2)先分别求得左、右子树的深度
(3)求得左、右子树的深度，取其最大值，然后加+1 ,即为二叉树的深度。
求二叉树的节点个数
(1)二叉树的深度应为其左、右子树节点个数的和+1。
(2)若二叉树为空，节点个数为零
(3)求得二叉树左、右子树的节点个数，二叉树的节点个数为左右子树节点个数之和+1。

程序代码

#include <stdio.h>
#include <malloc.h>
typedef int Status ;
typedef char TElemType;
#define ERROR 0
#define OK 1
typedef struct  BiTNode {//定义二叉链表
      TElemType      data;
      struct BiTNode   *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

Status CreateBiTree(BiTree &T)//按照先序顺序（根——左——右），生成一个二叉树，参数为根节点T的引用
{
    char ch;
scanf("%c",&ch);
//if(ch==' ')T=NULL;
if(ch=='#')T=NULL;//若输入的ch为’#’，则认为该节点为空，此处不使用’space’的原因为空格不易识别
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));//为节点申请新的存储空间
        T->data=ch;//将输入的ch赋给T的数据域
        CreateBiTree(T->lchild);//生成左子树
        CreateBiTree(T->rchild);//生成右子树，顺序符合先序顺序，左子树和右子树分别都是二叉树，进行递归调用，
    }
    return OK;
}
Status Visit(TElemType e)//Visit函数，简单的遍历函数，输出节点数据域的值，参数为e
{
    printf("%c ",e);
    return OK;
}
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) // 先序遍历二叉树，参数为根节点的指针T以及Visit函数
{
  if (T){//根——左——右
     if (Visit(T->data))
        if (PreOrderTraverse(T->lchild,Visit))//遍历左子树
            if (PreOrderTraverse(T->rchild,Visit))//遍历右子树
               return OK;
      return ERROR;
  }else    return OK;
}//PreOrderTraverse

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//中序遍历二叉树
{

  if (T){// 左——根——右
        if (InOrderTraverse(T->lchild,Visit))//遍历左子树
            if (Visit(T->data))
                if (InOrderTraverse(T->rchild,Visit))//遍历右子树
               return OK;
      return ERROR;
  }else    return OK;

}//InOrderTraverse
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) //后序遍历二叉树
{
  if (T){//左——右——根
     if (PostOrderTraverse(T->lchild,Visit))//遍历左子树
        if (PostOrderTraverse(T->rchild,Visit))//遍历右子树
            if (Visit(T->data))
               return OK;
      return ERROR;
  }else    return OK;
  printf("\n");
}//PostOrderTraverse
void Countleaf(BiTree T, int &count)//求叶子节点的个数，参数为根节点的指针T以及计数变量count，无返回值
{
  if (T){
     if((T->lchild==NULL)&&(T->rchild==NULL))
++count;//若某节点左子树与右子树都为空，那么该节点为叶子节点，计数变量count加1
      Countleaf( T->lchild,count);
      Countleaf( T->rchild,count);
  }
}//Countleaf
int BiTreeDepth(BiTree T) //  返回二叉树的深度, 参数为树根的指针T，返回值为二叉树的深度depthval
{
    int depthval,depthLeft,depthRight;//定义三个整型变量，分别为二叉树的深度、左子树的深度以及右子树的深度
   if (!T)depthval = 0;//若二叉树为空，则深度为0
   else
   {
        depthLeft=BiTreeDepth(T->lchild);//求左子树的深度
        depthRight=BiTreeDepth(T->rchild);//求右子树的深度，左右子树分别又都是二叉树，进行递归调用
		//if(depthLeft>depthRight)
        //    depthval=1+depthLeft;
        //else
        //    depthval=1+depthRight;
        depthval=1+(depthLeft>depthRight?depthLeft:depthRight);//二叉树的深度为左子树的深度和右子树的深度中较大的那个再加1.
   }
   return depthval;
}
int BiTreeSize(BiTree T)
{
    if(T==NULL)
        return 0;
    else
        return 1+BiTreeSize(T->lchild)+BiTreeSize(T->rchild);
}

int main()
{
    int c=0,depth,size;
    BiTNode *T;
    printf("Please input a bitree:('#'--NULL):\n");
    CreateBiTree(T);//生成二叉树
    printf("PreOrderTraverse:\n");
    PreOrderTraverse(T,Visit);printf("\n");//先序遍历
    printf("InOrderTraverse:\n");
    InOrderTraverse(T,Visit);printf("\n");//中序遍历
    printf("PostOrderTraverse:\n");
    PostOrderTraverse(T,Visit);printf("\n");//后序遍历
    Countleaf(T,c);//求叶子节点个数
    printf("The num of the leafnode:%d",c);
    depth=BiTreeDepth(T);printf("\n");//求二叉树深度
    printf("The Depth of the BiTree:%d",depth);
    size=BiTreeSize(T);printf("\n");//求二叉树结点个数
    printf("The Size of the BiTree:%d",size);printf("\n");
    return 0;
}