C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析

這篇文章主要介紹C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

公司主營業(yè)務(wù)：成都做網(wǎng)站、成都網(wǎng)站設(shè)計、成都外貿(mào)網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)公司推出濱湖免費做網(wǎng)站回饋大家。

C++ 數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷

完全二叉樹（Complete Binary Tree）：若設(shè)二叉樹的深度為h,除第h層外，其他各層（1~h-1）的節(jié)點數(shù)都達到最大個數(shù)，第h層所有的節(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。完全二叉樹由滿二叉樹而引起來的。對于深度為K的，有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)每一個節(jié)點都與深度為K的滿二叉樹中編號從1到n的節(jié)點一一對應(yīng)時稱之為完全二叉樹。

注意：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

完全二叉樹的特點：完全二叉樹的效率極高，堆是一種完全二叉樹或者近似完全二叉樹，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優(yōu)化。

判斷完全二叉樹的方法：從上圖我們可以看出，完全二叉樹可能會出現(xiàn)以下情況：左子樹存在，右子樹不存在；左子樹存在，有字數(shù)存在；左、右子樹都不存在；所以我們可以利用廣度優(yōu)先遍歷（層序遍歷）將二叉樹進行遍歷，設(shè)置一個標志位，當(dāng)遇到一個空節(jié)點時，將標志位為修改；當(dāng)后面在遇到有效節(jié)點并且標志位被修改時，則該二叉樹不是完全二叉樹。

當(dāng)該二叉樹為空時、修改標志位后無有效節(jié)點時，該二叉樹為完全二叉樹。

代碼實現(xiàn)：

#include<iostream> 
using namespace std; 
#include<queue> 
 
template<class T> 
struct TreeNode //二叉樹結(jié)點 
{ 
  T _value; 
  TreeNode<T>* _left; 
  TreeNode<T>* _right; 
  TreeNode(const T& value) 
    :_value(value) 
    , _left(NULL) 
    , _right(NULL) 
  {} 
}; 
 
 
template<class T> 
bool Is_completeTree(TreeNode<T>* node) 
{ 
  queue<TreeNode<T>*> q; 
  if (node != NULL) 
  { 
    q.push(node); 
    TreeNode<T>* cur = NULL; 
    bool flag = false; //設(shè)置標志位 
    while (!q.empty()) 
    { 
      cur = q.front(); 
      q.pop(); 
      if (cur) 
      { 
        if (flag) 
          return false; 
        q.push(cur->_left); 
        q.push(cur->_right); 
      } 
      else 
        flag = true; //修改標志位 
    } 
    return true; 
  } 
  return true; 
}

以上是“C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁名稱：C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析
URL地址：http://muchs.cn/article42/ijoiec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、做網(wǎng)站、軟件開發(fā)、企業(yè)建站、網(wǎng)頁設(shè)計公司、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)