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++ # 数据结构完全二叉树的判断 # 完全二叉树 # C++二叉树结构的建立与基本操作 # c++二叉树的几种遍历算法 # C++非递归建立二叉树实例 # C++实现二叉树遍历序列的求解方法 # C++实现二叉树基本操作详解 # C++ 遍历二叉树实例详解 # C++合并二叉树的思路与示例代码 # 二叉树 # 子树 # 遍历 # 是一种 # 都不 # 这就是 # 我们可以 # 数据结构 # 希望能 # 要用 # 不存在 # 可以看出 # 极高 # 谢谢大家 # 都与 # 为空 # 上图 # 称之为 # 则该 # pre

返回目录在线咨询

上一篇：Golang如何实现REST API接口_Golang REST API接口开发实践
下一篇：全球贸易新趋势，探索外贸网站成功秘诀

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C++ 数据结构完全二叉树的判断

您的项目需求