快捷導(dǎo)航

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

更新時間：2017年06月06日 17:15:33 作者：BabysBreath_hl

這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷的相關(guān)資料,需要的朋友可以參考下

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

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

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

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

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

當(dāng)該二叉樹為空時、修改標(biāo)志位后無有效節(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è)置標(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; 
}

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

您可能感興趣的文章: