服务器之家

服务器之家 > 正文

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

时间:2021-05-16 17:54     来源/作者:BabysBreath_hl

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

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

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

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

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

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

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

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/he_shuai20/article/details/71189854

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部