树：求二叉树的高度和叶子结点数量

ゝ一世哀愁。 2022-05-31 10:28 199阅读 0赞

**算法代码很简单都是用使用递归计算，大家把递归思想领悟到就ok了**。

# 二叉树高度算法 #

//求二叉树的高度 采用递归的方式
    void GetHeight(BiTree tree, int* heightNum)
    {
    	if (NULL != tree)
    	{
    		int LHeight;
    		int RHight;
    		GetHeight(tree->lchild,&LHeight);
    		GetHeight(tree->rchild,&RHight);
    		*heightNum = LHeight > RHight ? LHeight + 1 : RHight + 1;
    	}
    	else
    	{
    		*heightNum = 0;
    	}
    }

#    二叉树叶子结点数量算法 #

//求二叉树的叶子结点 采用递归的方式计算叶子结点个数
    void GetLeaf(BiTree tree,int* leafNum)
    {
    	if (NULL != tree)
    	{
    		if (tree->lchild == NULL && tree->rchild == NULL)
    		{
    			*leafNum += 1;
    		}
    		GetLeaf(tree->lchild,leafNum);
    		GetLeaf(tree->rchild,leafNum);
    	}
    }

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    typedef char EleType;
    typedef struct BiTNode
    {
    	EleType data;//数据结点数据域
    	struct BiTNode	*lchild, *rchild;//左孩子，右孩子结点指针域
    }BiTNode,*BiTree;
    
    //约定通过前序遍历创建结点
    //每个结点都有左右孩子，孩子不存在为NULL
    void CreatBiTree(BiTree* tree)
    {
    	char c;
    	scanf("%c",&c);
    	if (' '== c)
    	{
    		*tree = NULL;
    	}
    	else
    	{
    		*tree = (BiTNode*)malloc(sizeof(BiTNode));
    		(*tree)->data = c;
    		CreatBiTree(&(*tree)->lchild);//创建左子树
    		CreatBiTree(&(*tree)->rchild);//创建右子树
    	}
    }
    void VisitNode(EleType data)
    {
    	printf("%c ", data);
    	return;
    }
    //前序遍历
    void PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		VisitNode(tree->data);
    		PreOrderTraverse(tree->lchild);
    		PreOrderTraverse(tree->rchild);
    	}
    }
    
    //求二叉树的叶子结点 采用递归的方式计算叶子结点个数
    void GetLeaf(BiTree tree,int* leafNum)
    {
    	if (NULL != tree)
    	{
    		if (tree->lchild == NULL && tree->rchild == NULL)
    		{
    			*leafNum += 1;
    		}
    		GetLeaf(tree->lchild,leafNum);
    		GetLeaf(tree->rchild,leafNum);
    	}
    }
    //求二叉树的高度 采用递归的方式
    void GetHeight(BiTree tree, int* heightNum)
    {
    	if (NULL != tree)
    	{
    		int LHeight;
    		int RHight;
    		GetHeight(tree->lchild,&LHeight);
    		GetHeight(tree->rchild,&RHight);
    		*heightNum = LHeight > RHight ? LHeight + 1 : RHight + 1;
    	}
    	else
    	{
    		*heightNum = 0;
    	}
    }
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请按前序遍历的方式输入结点数据，孩子结点为NULL用空格代替：");
    	CreatBiTree(&tree);
    	printf("前序遍历：");
    	PreOrderTraverse(tree);
    	int heightNum,leafNum = 0;
    	GetLeaf(tree, &leafNum);
    	GetHeight(tree, &heightNum);
    	printf("\n二叉树的高度:%d", heightNum);
    	printf("\n二叉树的叶子结点数目:%d",leafNum);
    	printf("\n");
    	return 0;
    }

# 运行结果测试 #

我们下图的二叉树进行测试。

![Center][]

运行结果如下，注意：我们创建结点时的前序输入:ABC\_\_D\_\_EF\_\_G\_\_，一个\_表示一个空格哟。

![Center 1][]

[Center]: /images/20220531/bbf64cc622c4474abd040774eeb7148d.png
[Center 1]: /images/20220531/d4a3a9f473734cb58234098b84638ffb.png