C++判断一棵树是否为完全二叉树(CBT)

2023-11-23 04:59

本文主要是介绍C++判断一棵树是否为完全二叉树(CBT),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 定义

如果一棵深度为k,有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。(只有最下两层结点可以度小于2)。

需要满足以下二个特征:

  1. 叶子结点只可能在层次最大的两层上出现;

  2. 前k-1层中的结点都是“满”的,且第 k 层的结点都集中在左边。

2. 思路

层序遍历的时候我们都是只把不为空的左右孩子送入队列中,现在我们把层序遍历到的每个节点的左右孩子不管为空还是不为空都送入队列中,若为完全二叉树,则不断的pop(),当遇到第一个为空的结点后,队列中剩下的结点应该都为空,若海域非空的结点,则不是完全二叉树。

更详细的例子可以参考这篇博客:判断一棵树是否是完全二叉树
我们主要代码也是参考这里的~

3. 代码

#include <iostream>
#include <queue>struct Node {int value;Node* left;Node* right;Node(int value):value(value), left(nullptr), right(nullptr) {}
};bool isCBT(Node* head) {if (head == nullptr) {return true;}std::queue<Node*> qcbt;qcbt.push(head);Node* front = nullptr;while (front = qcbt.front()) {  // not ==, return we first encount nullptrqcbt.push(front->left);qcbt.push(front->right);qcbt.pop();}while(!qcbt.empty()) {if (qcbt.front() != nullptr) {  // if we encount a not nullptr, return fasereturn false;}qcbt.pop();}return true;    // if pass the check, is CBT!
}int main() {Node* head1 = new Node(1);head1->left = new Node(2);head1->right = new Node(3);head1->left->right = new Node(4);head1->right->right = new Node(5);std::cout << "==============CBT Test1==============\n";bool iscbt1 = isCBT(head1);std::cout << iscbt1 << std::endl;Node* head2 = new Node(1);head2->left = new Node(2);head2->right = new Node(3);head2->left->left = new Node(4);head2->left->right = new Node(5);head2->right->left = new Node(6);std::cout << "==============CBT Test2==============\n";bool iscbt2 = isCBT(head2);std::cout << iscbt2 << std::endl;return 0;
}

在这里插入图片描述

4. 参考

  1. 数据结构面试题/判断一棵树是否是完全二叉树
  2. 数据结构之判断一棵树是否为完全二叉树

今天写的都是二叉树相关的,什么BST,AVL,DFS,BFS,CBT等等。上次网易游戏提前批二面就是问的一道线索二叉树相关的题目,奈何当时没有复习到。

这篇关于C++判断一棵树是否为完全二叉树(CBT)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/415519

相关文章

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳:精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC

shell脚本快速检查192.168.1网段ip是否在用的方法

《shell脚本快速检查192.168.1网段ip是否在用的方法》该Shell脚本通过并发ping命令检查192.168.1网段中哪些IP地址正在使用,脚本定义了网络段、超时时间和并行扫描数量,并使用... 目录脚本:检查 192.168.1 网段 IP 是否在用脚本说明使用方法示例输出优化建议总结检查 1

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode(VSCode)中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境:详细教程1. 什么是 VSCode?2. 安装 VSCo

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数