C++中数据结构完全二叉树的判断分析-创新互联

这篇文章主要介绍C++中数据结构完全二叉树的判断分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

创新互联公司是专业的昌江黎族网站建设公司,昌江黎族接单;提供成都网站建设、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行昌江黎族网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

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

完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树。完全二叉树由满二叉树而引起来的。对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。

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

注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。

完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二叉树或者近似完全二叉树,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化。

判断完全二叉树的方法:从上图我们可以看出,完全二叉树可能会出现以下情况:左子树存在,右子树不存在;左子树存在,有字数存在;左、右子树都不存在;所以我们可以利用广度优先遍历(层序遍历)将二叉树进行遍历,设置一个标志位,当遇到一个空节点时,将标志位为修改;当后面在遇到有效节点并且标志位被修改时,则该二叉树不是完全二叉树。

当该二叉树为空时、修改标志位后无有效节点时,该二叉树为完全二叉树。

代码实现:

#include 
using namespace std; 
#include 
 
template 
struct TreeNode //二叉树结点 
{ 
  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; //设置标志位 
    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++中数据结构完全二叉树的判断分析”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注创新互联网站建设公司行业资讯频道!

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网站标题:C++中数据结构完全二叉树的判断分析-创新互联
路径分享:http://myzitong.com/article/doojhe.html