- 相干保举
C++若何完成二叉树叶子节点个数计较
良多人都不晓得C++若何完成二叉树叶子节点个数计较，上面小编为大师解答一下，但愿能帮到大师！
/*求二叉树叶子节点个数 -- 接纳递归和非递归体例
经调试可运转源码及阐发以下：
***/
#include
#include
#include
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;
stackst;
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++若何完成二叉树叶子节点个数计较】相干文章：
C++若何挪用matlab函数06-29
C++完成自底向上的合并排序算法09-09
c和c++中完成函数回调的体例08-30
C说话入彀较二叉树宽度的体例06-12
若何完成硬盘对拷06-30
WPS表格怎样计较多个数的乘积08-01
若何完成CSS右对齐10-29
PHP中多态若何完成09-04
若何完成表格窗口的牢固10-04
计较机二级C++模板概述07-06