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++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.

C++中std::distance使用方法示例

《C++中std::distance使用方法示例》std::distance是C++标准库中的一个函数,用于计算两个迭代器之间的距离,本文主要介绍了C++中std::distance使用方法示例,具... 目录语法使用方式解释示例输出:其他说明:总结std::distance&n编程bsp;是 C++ 标准

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑