C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法。本站提示廣大學習愛好者:(C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法)文章只能為提供參考,不一定能成為您想要的結果。以下是C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法正文
作者:難免有錯_
這篇文章主要介紹了C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法,涉及C++二叉樹的定義、遍歷、統計相關操作技巧,需要的朋友可以參考下本文實例講述了C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法。分享給大家供大家參考,具體如下:
/*求二叉樹葉子節點個數 -- 采用遞歸和非遞歸方法 經調試可運行源碼及分析如下: ***/ #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; /* 求二叉樹葉子節點數 葉子節點:即沒有左右子樹的結點 遞歸方式步驟: 如果給定節點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; stack <BTreeNode*> st; while (proot != NULL || !st.empty()) { while (proot != NULL) { cout << "節點:" << 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; } /*初始化二叉樹根節點*/ 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++程序設計有所幫助。