二叉树叶子结点个数统计

1.问题描述：

输入一棵二叉树，求出其叶子结点个数。

2.实验要求：

（1）设计二叉树的二叉链表存储结构

（2）设计求叶子结点个数的递归算法

（3）输入一棵二叉树

（4）输出二叉树的叶子节点个数

示例：

ab#c##d##

二叉树叶子结点个数为：

3.程序实现：

(1)代码：

#include
using namespace std;
//二叉树结点
typedef struct BTNode 
{
	char root;
	struct BTNode* lchild;
	struct BTNode* rchild;
}BTree;

//创建二叉树
BTree* CreateBinaryTree() 
{
	char ch;
	cin >> ch;
	BTree* node;

	if (ch == '#') {
		node = NULL;
	}
	else {
		node = (BTree*)malloc(sizeof(BTree));
		if (ch) {
			node->root = ch;
			node->lchild = CreateBinaryTree();
			node->rchild = CreateBinaryTree();
		}
	}
	return node;
}

//二叉树叶子结点个数
int CountLeaf(BTree* root, int* count) 
{
	if (root != NULL && root->lchild == NULL && root->rchild == NULL) {
		(*count)++;
	}

	if (root != NULL) {
		CountLeaf(root->lchild, count);
		CountLeaf(root->rchild, count);
	}
	return *count;
}

int main() 
{
	//创建二叉树
	BTree* root = CreateBinaryTree();

	//二叉树叶子结点个数
	int count = 0;
	cout << "二叉树叶子结点个数为：" << CountLeaf(root, &count) << endl;
	return 0;
}

（2）算法理解：

先定义好二叉树的存储结构，然后再建立一个二叉树，最后运用递归求出叶子结点。

4.测试与运行：

 5.思考题：

如何设计非递归算法求叶子结点的个数？设计相关算法

使用队列和栈，可以将递归算法转换成非递归算法
在递归算法中，需要重复调用函数时，在非递归算法中，就需要入栈，进入下一层。
在递归算法中，返回调用函数的结果时，在非递归算法中，就需要出栈，返回到上一层。

int Count_BiTree0(BiTree T)
{
    int top=-1;     //此时栈为空
    int count =0;   
    BiTree S[MaxSize];
 
    while(T!=NULL || top != -1)
    {
        while (T != NULL)
        {
            if(T->lchild == NULL && T->rchild == NULL)
            {
                count++;
            }
            S[++top] = T;   //++top(top初始为-1),then将当前的根节点入栈
            T = T->lchild;  //访问当前根节点的左子树
        }
        if(top != -1)
        {
            T = S[top--];   //获取当前的根节点
            T = T->rchild;  //访问当前根节点的右子树
        }
    }
 
    return count;
}

原文链接：https://blog.csdn.net/h420405961/article/details/120816477

6.实验心得体会：
熟练掌握二叉树的结点结构，理解并运用如何创建一棵二叉树。掌握递归方法。理解指针的使用，必须指向同类型的值，不可以出现野指针。创建函数时，注意形参和实参的统一。