二叉树叶子结点个数统计

这篇具有很好参考价值的文章主要介绍了二叉树叶子结点个数统计。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.问题描述:

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

2.实验要求:

(1)设计二叉树的二叉链表存储结构

(2)设计求叶子结点个数的递归算法

(3)输入一棵二叉树

(4)输出二叉树的叶子节点个数

示例:

ab#c##d##

二叉树叶子结点个数为:

3.程序实现:

(1)代码:

#include<iostream>
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.实验心得体会:
熟练掌握二叉树的结点结构,理解并运用如何创建一棵二叉树。掌握递归方法。理解指针的使用,必须指向同类型的值,不可以出现野指针。创建函数时,注意形参和实参的统一。文章来源地址https://www.toymoban.com/news/detail-428304.html

到了这里,关于二叉树叶子结点个数统计的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包