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
*/
-
初學C語言的人最常問的幾個問題
C語言是一門通用計算機編程語言,應用廣泛。對於新手來説學習C語言並不是那麼容易,下面是C語言初學者最常問的幾個問題,歡迎閲讀!1.多久能學會編程?這是一個沒有答案的問題。每個人投入的時間、學習效率和基礎都不一樣。如果你每天都拿出大把的時間來學習,那麼兩三...
-
為什麼入門首選C語言?
C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。對於大部分程序員,C語言是學習編程的第一門語言,很少有不瞭解C的程序員。那麼為什麼入門首選C語言呢,下面小編為大家介紹一下吧!C...
-
2017年計算機二級C語言的應用
yjbys考試網為您整理了2017年計算機二級C語言的應用,更多計算機等級考試相關信息請訪問應屆畢業生計算機等級考試網。從前面對C語言的特點的分析中,不難看出C語言具有編程方便、語句簡練、功能很強、移植性好等優點,是編程者喜歡使用的一種結構化程序設計語言。C...
-
c語言如何控制硬件
你們知道在C語言中如何控制計算機的硬件嗎?下面是應屆畢業生小編帶來的關於c語言如何控制硬件的內容,歡迎閲讀!c語言如何控制硬件?C語言是沒辦法控制硬件的首先,C語言不能夠直接對硬件進行操作。從本質上來説,連彙編語言都不可以。只有機器語言能夠直接操作硬件。...