C/C++递归算法，计算二叉树中叶子结点的数目

关键思路：叶子结点的度为0，即没有左孩子和右孩子

关键代码：

int searchNum(BiTree T)
{
	if (!T) return 0;
	else
	{
		int l, r;
		l=searchNum(T->lchild);
		r=searchNum(T->rchild);
		if ((l == 0 && r == 0))//判断是否遍历到度为0及叶子结点
			number++;
		return 1;
	}
}

代码实现：

头文件的实现

#pragma once
#include
#define OK 1;
#define ERROR 0;
typedef  char  TElemType;
int  number;//记录叶子结点的个数
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode* lchild, * rchild;

}BiTNode, * BiTree;//二叉树的准备工作
int creatTree(BiTree& T);//初始化二叉树
int searchNum(BiTree T);//遍历二叉树
void print();//输出二叉树的叶子结点个数

函数的实现

#include"标头.h"
using namespace std;
int number = 0;
int creatTree(BiTree& T)
{
	char m;
	scanf_s("%c", &m);
	if (m == ' ')//若输入的为空格，则表示该结点为空
	{
		T = NULL;
		return 0;
	}
	else
	{
		T = (BiTree)malloc(sizeof(BiTNode));//输出不为空格，这初始话该结点
		T->data = m;
		creatTree(T->lchild);//再初始化左孩子
		creatTree(T->rchild);//再初始化右孩子
		return OK;
	};
}
int searchNum(BiTree T)//遍历二叉树
{
	if (!T) return 0;
	else
	{
		int l, r;
		l=searchNum(T->lchild);
		r=searchNum(T->rchild);
		if ((l == 0 && r == 0))//判断是否遍历到度为0及叶子结点
			number++;
		return 1;
	}
}
void print()//输出二叉树的叶子结点个数
{
	cout << number << endl;
}

主函数的调用

#include"标头.h"
int main()
{
	BiTree T;
	creatTree(T);
	searchNum(T);
	print();
	return 0;
}