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;
}

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

赞 (0)

相关推荐

  • C++ 数据结构之水洼的数量算法

    C++ 数据结构之水洼的数量算法 题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼. 使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止. 则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N). 代码: /* * main.cpp * * Created on: 2014.7.12 *本栏目更多精彩内容:http://ww

  • C++ 冒泡排序数据结构、算法及改进算法

    程序代码如下: 复制代码 代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define  MAXNUM 20template<typename T>void Swap(T& a, T& b){    int t = a;    a = b;    b

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++

  • C++ 数据结构 堆排序的实现

    C++ 数据结构 堆排序的实现

    堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下

  • C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C++语言数据结构 串的基本操作实例代码

    C++语言数据结构 串的基本操作实例代码

    C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================

  • C++数据结构之文件压缩（哈夫曼树）实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

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

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

    C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二

  • 判断二叉树是否为完全二叉树的实例

    完全二叉树特点 完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的.最后一层如果也满了,是一颗满二叉树,也是完全二叉树.最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树. 判断一棵二叉树是否为完全二叉树 import java.util.*; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = v

  • 利用go语言判断是否是完全二叉树

    利用go语言判断是否是完全二叉树

    目录 一.什么是完全二叉树? 二.流程 三.代码 1.树节点 2.测试代码 3.判断树是否为完全二叉树代码 4.代码解读 5.运行结果 一.什么是完全二叉树? 先看如下这一张图: 这个一颗二叉树,如何区分该树是不是完全二叉树呢? 当一个节点存在右子节点但是不存在左子节点这颗树视为非完全二叉树 当一个节点的左子节点存在但是右子节点不存在视为完全二叉树 如果没有子节点,那也是要在左侧开始到右侧依次没有子节点才视为完全二叉树,就像上图2中 而上面第一张图这颗二叉树很明显是一颗非完全二叉树,因为在第三层

  • Java 数据结构进阶二叉树题集上

    Java 数据结构进阶二叉树题集上

    目录 1.二叉树的遍历 (1)前.中.后序遍历 (2)层序遍历 2.获取树中子结点的个数 3.获取二叉树的高度 4.判断是不是完全二叉树 5.判断两个树是否相同 6.另一棵树的子树 7.判断平衡二叉树 二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解.(上)中的题偏向于基础,后面(下)中的题机会比较难. 1.二叉树的遍历 (1)前.中.后序遍历 这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码.以前序遍历为例: 如果根节点root为

  • go语言中布隆过滤器低空间成本判断元素是否存在方式

    go语言中布隆过滤器低空间成本判断元素是否存在方式

    目录 简介 原理 数据结构 添加 判断存在 哈希函数 布隆过滤器大小.哈希函数数量.误判率 应用场景 数据库 黑名单 实现 数据结构 初始化 添加元素 判断元素是否存在 简介 布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快. 但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回true只是表示元素可能存在集合内,返回false则表示元素一定不存在集合内.因此适合用于能够容忍一定误判元素存在集合内的场景,比如缓存

  • Redis 中的布隆过滤器的实现

    什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中.很常用的一个功能是用来去重.在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?简单点可以爬虫每采集过一个 URL,就把这个 URL 存入数据库中,每次一个新的 URL 过来就到数据库查询下是否访问过. select id from table where url = 'https://jaychen.cc' 但是随着爬虫爬过的 URL 越来越多,每次请求前都要访问数据

  • 详解go语言中sort如何排序

    目录 sort包源码解读 前言 如何使用 基本数据类型切片的排序 自定义Less排序比较器 自定义数据结构的排序 分析下源码 不稳定排序 稳定排序 查找 Interface 总结 参考 sort 包源码解读 前言 我们的代码业务中很多地方需要我们自己进行排序操作,go 标准库中是提供了 sort 包是实现排序功能的,这里来看下生产级别的排序功能是如何实现的. go version go1.16.13 darwin/amd64 如何使用 先来看下 sort 提供的主要功能 对基本数据类型切片的排序

  • MYSQL事务的隔离级别与MVCC

    MYSQL事务的隔离级别与MVCC

    目录 前言 1. 事务(transaction)的起源 1.1. 事务的定义 1.2. 哪些存储引擎支持事务 2. MySQL的事务语法 2.1. 自动提交 2.2. 手动操作事务 2.2.1. 开启事务 2.2.2. 提交或回滚 2.3. autocommit系统变量 3. 事务并发执行导致的读问题 3.1. 脏读 3.2. 不可重复读 3.3. 幻读 4. 回答一些可能存在的问题 5. SQL标准与4种隔离级别 5.1. 为什么要设置隔离级别? 5.2. 蹩脚的中文翻译 5.3. 为什么单单

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言数据结构之判断循环链表空与满

    C语言数据结构之判断循环链表空与满 前言: 何时队列为空?何时为满? 由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等.因此,我们无法通过front=rear来判断队列"空"还是"满". 注:先进入的为'头',后进入的为'尾'. 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的空和满: 其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始

随机推荐