C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法
5星 · 超过95%的资源 48 浏览量
2020-08-30
13:32:54
上传
评论 2
收藏 37KB PDF 举报 
C++使用递归和非递归算法实现的二叉树叶子节点个数计算方使用递归和非递归算法实现的二叉树叶子节点个数计算方
法法
主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统
计相关操作技巧,需要的朋友可以参考下
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考，具体如下：
/*求二叉树叶子节点个数 -- 采用递归和非递归方法
经调试可运行源码及分析如下：
***/
#include <stdlib.h>
#include <iostream>
#include <stack>
using std::cout;
using std::cin;
using std::endl;
using std::stack;
/*二叉树结点定义*/
typedef struct BTreeNode
{
char elem;
struct BTreeNode *pleft;
struct BTreeNode *pright;
}BTreeNode;
/*
求二叉树叶子节点数
叶子节点：即没有左右子树的结点
递归方式步骤：
如果给定节点proot为NULL，则是空树，叶子节点为0，返回0；
如果给定节点proot左右子树均为NULL，则是叶子节点，且叶子节点数为1，返回1；
如果给定节点proot左右子树不都为NULL，则不是叶子节点，以proot为根节点的子树叶子节点数=proot左子树叶子节点数+proot右子树叶子节点数。
/*递归实现求叶子节点个数*/
int get_leaf_number(BTreeNode *proot)
{
if(proot == NULL)
return 0;
if(proot->pleft == NULL && proot->pright == NULL)
return 1;
return (get_leaf_number(proot->pleft) + get_leaf_number(proot->pright));
}
/*非递归：本例采用先序遍历计算
判断当前访问的节点是不是叶子节点，然后对叶子节点求和即可。
**/
int preorder_get_leaf_number(BTreeNode* proot)
{
if(proot == NULL)
return 0;
int num = 0;
stack <BTreeNode*> st;
while (proot != NULL || !st.empty())
{
while (proot != NULL)
{
cout << "节点：" << proot->elem << endl;
st.push(proot);
proot = proot->pleft;
}
if (!st.empty())
{
proot = st.top();
st.pop();
if(proot->pleft == NULL && proot->pright == NULL)
num++;
proot = proot -> pright;
}
}
return num;
}
/*初始化二叉树根节点*/
BTreeNode* btree_init(BTreeNode* &bt)
{
bt = NULL;
return bt;
}
/*先序创建二叉树*/
void pre_crt_tree(BTreeNode* &bt)
资源评论
杏花朵朵2023-07-29这篇文件的算法实现简洁明了，让人能够轻松理解和应用。
优游的鱼2023-07-29这个文件提供了一种有效的方式来计算二叉树的叶子节点个数，让人更加深入了解了二叉树结构的特点。
大禹倒杯茶2023-07-29这个文件给出了使用递归和非递归算法计算二叉树叶子节点的两种方法，帮助读者选择适合自己的方式。
H等等H2023-07-29这个文件提供了一个简单但有效的方法来计算二叉树的叶子节点个数，非常实用。
KateZeng2023-07-29这篇文章介绍了一种快速准确计算二叉树叶子节点个数的方法，适合初学者入门。
