程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法

C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法

編輯:關於C++

C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法。本站提示廣大學習愛好者:(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++程序設計有所幫助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved