C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法
本文實(shí)例講述了C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法。分享給大家供大家參考,具體如下:
/*求二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) -- 采用遞歸和非遞歸方法 經(jīng)調(diào)試可運(yùn)行源碼及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> 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; stack <BTreeNode*> st; 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 */
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
C++入門(mén)到精通之循環(huán)語(yǔ)句的使用教程
這篇文章主要給大家介紹了關(guān)于C++中循環(huán)語(yǔ)句的用法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05C++中一維數(shù)組與指針的關(guān)系詳細(xì)總結(jié)
以下是對(duì)C++中一維數(shù)組與指針的關(guān)系進(jìn)行了詳細(xì)的總結(jié)介紹,需要的朋友可以過(guò)來(lái)參考下2013-09-09C++實(shí)現(xiàn)LeetCode(59.螺旋矩陣之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語(yǔ)言中對(duì)字母進(jìn)行大小寫(xiě)轉(zhuǎn)換的簡(jiǎn)單方法
這篇文章主要介紹了C語(yǔ)言中對(duì)字母進(jìn)行大小寫(xiě)轉(zhuǎn)換的簡(jiǎn)單方法,是C語(yǔ)言入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-10-10C++初學(xué)者之根據(jù)輸入的任何一個(gè)正整數(shù),輸出可能被表示的連續(xù)正整數(shù)
這篇文章主要介紹了C++初學(xué)者之根據(jù)輸入的任何一個(gè)正整數(shù),輸出可能被表示的連續(xù)正整數(shù)的相關(guān)資料,需要的朋友可以參考下2016-03-03C語(yǔ)言實(shí)現(xiàn)2048游戲(ege圖形庫(kù)版)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)2048游戲,ege圖形庫(kù)版,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-12-12