欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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++入門到精通之循環(huán)語句的使用教程

    C++入門到精通之循環(huán)語句的使用教程

    這篇文章主要給大家介紹了關于C++中循環(huán)語句的用法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-05-05
  • C++中一維數(shù)組與指針的關系詳細總結

    C++中一維數(shù)組與指針的關系詳細總結

    以下是對C++中一維數(shù)組與指針的關系進行了詳細的總結介紹,需要的朋友可以過來參考下
    2013-09-09
  • C++實現(xiàn)LeetCode(59.螺旋矩陣之二)

    C++實現(xiàn)LeetCode(59.螺旋矩陣之二)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-07-07
  • c_str()的用法詳細解析

    c_str()的用法詳細解析

    c_str()就是把string類對象轉換成和c兼容的char *類型。這是為了與c語言兼容,在c語言中沒有string類型,故必須通過string類對象的成員函數(shù)c_str()把string 對象轉換成c中的字符串樣式
    2013-09-09
  • C語言線索二叉樹基礎解讀

    C語言線索二叉樹基礎解讀

    線索二叉樹還是按照鏈二叉樹的方法創(chuàng)建,只不過在結點原本為空的左指針改為指向該結點在中序遍歷中的前驅,結點原本為空的右指針改為指向該結點在中序遍歷中的后繼,也就是說把空的指針給利用了起來
    2022-04-04
  • c語言冒泡排序和選擇排序的使用代碼

    c語言冒泡排序和選擇排序的使用代碼

    算法中排序是十分重要的,而每一個學習計算機的都會在初期的時候接觸到這種排序,下面這篇文章主要給大家介紹了關于c語言冒泡排序和選擇排序使用的相關資料,需要的朋友可以參考下
    2022-04-04
  • C語言中對字母進行大小寫轉換的簡單方法

    C語言中對字母進行大小寫轉換的簡單方法

    這篇文章主要介紹了C語言中對字母進行大小寫轉換的簡單方法,是C語言入門學習中的基礎知識,需要的朋友可以參考下
    2015-08-08
  • C語言單鏈表實現(xiàn)多項式相加

    C語言單鏈表實現(xiàn)多項式相加

    這篇文章主要為大家詳細介紹了C語言單鏈表實現(xiàn)多項式相加,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-10-10
  • C++初學者之根據(jù)輸入的任何一個正整數(shù),輸出可能被表示的連續(xù)正整數(shù)

    C++初學者之根據(jù)輸入的任何一個正整數(shù),輸出可能被表示的連續(xù)正整數(shù)

    這篇文章主要介紹了C++初學者之根據(jù)輸入的任何一個正整數(shù),輸出可能被表示的連續(xù)正整數(shù)的相關資料,需要的朋友可以參考下
    2016-03-03
  • C語言實現(xiàn)2048游戲(ege圖形庫版)

    C語言實現(xiàn)2048游戲(ege圖形庫版)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)2048游戲,ege圖形庫版,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-12-12

最新評論