C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法_求树的叶子节点个数

141 浏览量更新于2023-05-04 评论收藏 41KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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)

{

char ch;

cin >> ch;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38706055

粉丝: 5
资源: 909

会员权益专享

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

评论0

会员权益专享

最新资源

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

评论0

二叉树求叶子节点非递归

C++二叉树基本操作（求叶子结点数等）

非递归遍历完全二叉树 & 递归遍历完全二叉树

C++非递归求二叉树叶子节点个数

设计一算法，计算二叉树叶子结点总数。提示： int LeafCount ( BiTree T ) 如果是空树，则叶子结点个数为0; 否则，为：左子树的叶子结点个数＋右子树的叶子结点个数。

用C++编写递归算法，计算二叉树中叶子结点的数目。

请你以程序员的身份用C++语言编写可以运行的统计二叉树中结点个数和叶子结点个数的算法

用C++写通过二叉树的先序序列和中序序列构建二叉树,求叶子结点个数的递归和非递归算法

完成二叉树二叉链表结构的定义 ,实现二叉链表创建二叉树（尝试用递归算法实现），并实现先序、中序和后序遍历算法。实现二叉树求结点个数，求树的高度，求叶子结点数、交换二叉树左右子树的算法。

c++编写算法统计二叉树结点个数调试成功后写什么

非递归算法求二叉树的叶结点个数C++

用C++通过二叉树的先序序列和中序序列构建二叉树,求叶子结点个数的递归和非递归

编写算法计算二叉树中叶子结点数目c++

c++编写算法统计二叉树结点个数

用非递归算法求二叉树的叶结点个数c

会员权益专享

最新资源