C++中數據結構完全二叉樹的判斷分析

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

C++ 數據結構完全二叉樹的判斷

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

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

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

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

當該二叉樹為空時、修改標志位后無有效節點時，該二叉樹為完全二叉樹。

代碼實現：

#include<iostream> 
using namespace std; 
#include<queue> 
 
template<class T> 
struct TreeNode //二叉樹結點 
{ 
  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; //設置標志位 
    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++中數據結構完全二叉樹的判斷分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！