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

創(chuàng)新互聯(lián)公司是專業(yè)的昌江黎族網(wǎng)站建設(shè)公司，昌江黎族接單;提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行昌江黎族網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

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

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

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

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

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

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

代碼實(shí)現(xiàn)：

#include 
using namespace std; 
#include 
 
template 
struct TreeNode //二叉樹結(jié)點(diǎn) 
{ 
  T _value; 
  TreeNode* _left; 
  TreeNode* _right; 
  TreeNode(const T& value) 
    :_value(value) 
    , _left(NULL) 
    , _right(NULL) 
  {} 
}; 
 
 
template 
bool Is_completeTree(TreeNode* node) 
{ 
  queue*> q; 
  if (node != NULL) 
  { 
    q.push(node); 
    TreeNode* cur = NULL; 
    bool flag = false; //設(shè)置標(biāo)志位 
    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; //修改標(biāo)志位 
    } 
    return true; 
  } 
  return true; 
}

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站名稱：C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/doojhe.html