C++使用遞歸和非遞歸算法實現(xiàn)的二叉樹葉子節(jié)點個數(shù)計算方法
更新時間:2017年05月13日 08:52:28 作者:難免有錯_
這篇文章主要介紹了C++使用遞歸和非遞歸算法實現(xiàn)的二叉樹葉子節(jié)點個數(shù)計算方法,涉及C++二叉樹的定義、遍歷、統(tǒng)計相關操作技巧,需要的朋友可以參考下
本文實例講述了C++使用遞歸和非遞歸算法實現(xiàn)的二叉樹葉子節(jié)點個數(shù)計算方法。分享給大家供大家參考,具體如下:
/*求二叉樹葉子節(jié)點個數(shù) -- 采用遞歸和非遞歸方法 經調試可運行源碼及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉樹結點定義*/ typedef struct BTreeNode { char elem; struct BTreeNode *pleft; struct BTreeNode *pright; }BTreeNode; /* 求二叉樹葉子節(jié)點數(shù) 葉子節(jié)點:即沒有左右子樹的結點 遞歸方式步驟: 如果給定節(jié)點proot為NULL,則是空樹,葉子節(jié)點為0,返回0; 如果給定節(jié)點proot左右子樹均為NULL,則是葉子節(jié)點,且葉子節(jié)點數(shù)為1,返回1; 如果給定節(jié)點proot左右子樹不都為NULL,則不是葉子節(jié)點,以proot為根節(jié)點的子樹葉子節(jié)點數(shù)=proot左子樹葉子節(jié)點數(shù)+proot右子樹葉子節(jié)點數(shù)。 /*遞歸實現(xiàn)求葉子節(jié)點個數(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)); } /*非遞歸:本例采用先序遍歷計算 判斷當前訪問的節(jié)點是不是葉子節(jié)點,然后對葉子節(jié)點求和即可。 **/ 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é)點:" << 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; } /*初始化二叉樹根節(jié)點*/ BTreeNode* btree_init(BTreeNode* &bt) { bt = NULL; return bt; } /*先序創(chuàng)建二叉樹*/ 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é)點 pre_crt_tree(bt);//創(chuàng)建二叉樹 tree_leaf_number = get_leaf_number(bt);//遞歸 cout << "二叉樹葉子節(jié)點個數(shù)為:" << tree_leaf_number << endl; cout << "非遞歸先序遍歷過程如下:" << endl; tree_leaf_number = preorder_get_leaf_number(bt);//非遞歸 cout << "二叉樹葉子節(jié)點個數(shù)為:" << tree_leaf_number << endl; system("pause"); return 0; } /* 運行結果: a b c # # # d e # # f # # ---以上為輸入--- ---以下為輸出--- 二叉樹葉子節(jié)點個數(shù)為:3 非遞歸遍歷過程如下: 節(jié)點:a 節(jié)點:b 節(jié)點:c 節(jié)點:d 節(jié)點:e 節(jié)點:f 二叉樹葉子節(jié)點個數(shù)為:3 請按任意鍵繼續(xù). . . 本例創(chuàng)建的二叉樹形狀: a b d c e f */
希望本文所述對大家C++程序設計有所幫助。
相關文章
C++實現(xiàn)LeetCode(59.螺旋矩陣之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07C++初學者之根據(jù)輸入的任何一個正整數(shù),輸出可能被表示的連續(xù)正整數(shù)
這篇文章主要介紹了C++初學者之根據(jù)輸入的任何一個正整數(shù),輸出可能被表示的連續(xù)正整數(shù)的相關資料,需要的朋友可以參考下2016-03-03