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 || !y())
{
while (proot != NULL)
{
cout << "節點：" << proot->elem << endl;
(proot);
proot = proot->pleft;
}
if (!y())
{
proot = ();
();
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
*/
