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

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

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

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

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

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

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

#include<iostream> 
using namespace std; 
#include<queue> 
 
template<class T> 
struct TreeNode //二叉樹(shù)結(jié)點(diǎn) 
{ 
  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è)置標(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; 
} 

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！