本文实例讲述了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;
if (ch == '#')
{
bt = NULL;
}
else
{
bt = new BTreeNode;
bt->elem = ch;
pre_crt_tree(bt->pleft);
pre_crt_tree(bt->pright);
}
}
int main()
{
int tree_leaf_number = 0;
BTreeNode *bt;
btree_init(bt);//初始化根节点
pre_crt_tree(bt);//创建二叉树
tree_leaf_number = get_leaf_number(bt);//递归
cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl;
cout << "非递归先序遍历过程如下:" << endl;
tree_leaf_number = preorder_get_leaf_number(bt);//非递归
cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl;
system("pause");
return 0;
}
/*
运行结果:
a b c # # # d e # # f # #
---以上为输入---
---以下为输出---
二叉树叶子节点个数为:3
非递归遍历过程如下:
节点:a
节点:b
节点:c
节点:d
节点:e
节点:f
二叉树叶子节点个数为:3
请按任意键继续. . .
本例创建的二叉树形状:
a
b d
c e f
*/
希望本文所述对大家C++程序设计有所帮助。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。