- 相關(guān)推薦
C++如何實(shí)現(xiàn)二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算
很多人都不知道C++如何實(shí)現(xiàn)二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算，下面小編為大家解答一下，希望能幫到大家！
/*求二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) -- 采用遞歸和非遞歸方法
經(jīng)調(diào)試可運(yùn)行源碼及分析如下：
***/
#include
#include
#include
using std::cout;
using std::cin;
using std::endl;
using std::stack;
/*二叉樹(shù)結(jié)點(diǎn)定義*/
typedef struct BTreeNode
{
char elem;
struct BTreeNode *pleft;
struct BTreeNode *pright;
}BTreeNode;
/*
求二叉樹(shù)葉子節(jié)點(diǎn)數(shù)
葉子節(jié)點(diǎn)：即沒(méi)有左右子樹(shù)的結(jié)點(diǎn)
遞歸方式步驟：
如果給定節(jié)點(diǎn)proot為NULL，則是空樹(shù)，葉子節(jié)點(diǎn)為0，返回0；
如果給定節(jié)點(diǎn)proot左右子樹(shù)均為NULL，則是葉子節(jié)點(diǎn)，且葉子節(jié)點(diǎn)數(shù)為1，返回1；
如果給定節(jié)點(diǎn)proot左右子樹(shù)不都為NULL，則不是葉子節(jié)點(diǎn)，以proot為根節(jié)點(diǎn)的子樹(shù)葉子節(jié)點(diǎn)數(shù)=proot左子樹(shù)葉子節(jié)點(diǎn)數(shù)+proot右子樹(shù)葉子節(jié)點(diǎn)數(shù)。
/*遞歸實(shí)現(xiàn)求葉子節(jié)點(diǎn)個(gè)數(shù)*/
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));
}
/*非遞歸：本例采用先序遍歷計(jì)算
判斷當(dāng)前訪問(wèn)的節(jié)點(diǎn)是不是葉子節(jié)點(diǎn)，然后對(duì)葉子節(jié)點(diǎn)求和即可。
**/
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 << "節(jié)點(diǎn)：" << 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;
}
/*初始化二叉樹(shù)根節(jié)點(diǎn)*/
BTreeNode* btree_init(BTreeNode* &bt)
{
bt = NULL;
return bt;
}
/*先序創(chuàng)建二叉樹(shù)*/
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);//初始化根節(jié)點(diǎn)
pre_crt_tree(bt);//創(chuàng)建二叉樹(shù)
tree_leaf_number = get_leaf_number(bt);//遞歸
cout << "二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)為:" << tree_leaf_number << endl;
cout << "非遞歸先序遍歷過(guò)程如下：" << endl;
tree_leaf_number = preorder_get_leaf_number(bt);//非遞歸
cout << "二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)為:" << tree_leaf_number << endl;
system("pause");
return 0;
}
/*
運(yùn)行結(jié)果：
a b c # # # d e # # f # #
---以上為輸入---
---以下為輸出---
二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)為:3
非遞歸遍歷過(guò)程如下：
節(jié)點(diǎn)：a
節(jié)點(diǎn)：b
節(jié)點(diǎn)：c
節(jié)點(diǎn)：d
節(jié)點(diǎn)：e
節(jié)點(diǎn)：f
二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)為:3
請(qǐng)按任意鍵繼續(xù). . .
本例創(chuàng)建的二叉樹(shù)形狀：
a
b d
c e f
*/
【C++如何實(shí)現(xiàn)二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算】相關(guān)文章：
php如何實(shí)現(xiàn)的二叉樹(shù)遍歷(示例)10-17
C++ 實(shí)現(xiàn)2048游戲范例09-17
C++實(shí)現(xiàn)一維向量旋轉(zhuǎn)算法07-31
c++利用windows函數(shù)實(shí)現(xiàn)計(jì)時(shí)范例11-03
如何運(yùn)行C++程序08-28
C語(yǔ)言中實(shí)現(xiàn)參數(shù)個(gè)數(shù)可變函數(shù)11-12