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

C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法

 更新時(shí)間:2017年05月13日 08:52:28   作者:難免有錯(cuò)_  
這篇文章主要介紹了C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法,涉及C++二叉樹(shù)的定義、遍歷、統(tǒng)計(jì)相關(guān)操作技巧,需要的朋友可以參考下

本文實(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ǔ)句的使用教程

    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-05
  • C++中一維數(shù)組與指針的關(guān)系詳細(xì)總結(jié)

    C++中一維數(shù)組與指針的關(guān)系詳細(xì)總結(jié)

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

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

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

    c_str()的用法詳細(xì)解析

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

    C語(yǔ)言線索二叉樹(shù)基礎(chǔ)解讀

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

    c語(yǔ)言冒泡排序和選擇排序的使用代碼

    算法中排序是十分重要的,而每一個(gè)學(xué)習(xí)計(jì)算機(jī)的都會(huì)在初期的時(shí)候接觸到這種排序,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言冒泡排序和選擇排序使用的相關(guān)資料,需要的朋友可以參考下
    2022-04-04
  • C語(yǔ)言中對(duì)字母進(jìn)行大小寫(xiě)轉(zhuǎn)換的簡(jiǎn)單方法

    C語(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-08
  • C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加

    C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加

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

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

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

    C語(yǔ)言實(shí)現(xiàn)2048游戲(ege圖形庫(kù)版)

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

最新評(píng)論