当前位置:网站首页>Déterminer si un arbre binaire est un arbre binaire complet
Déterminer si un arbre binaire est un arbre binaire complet
2022-07-05 23:02:00 【Lumière du matin】
1、Titre
Compte tenu du noeud racine d'un arbre binaireroot
,Pour déterminer si cet arbre est un arbre binaire complet.
2、Analyse
Un arbre binaire complet est une couche pleine ou pleine,Si l'insatisfaction se remplit également de gauche à droite.
Pratique classique
Traverser par niveau,Suivez quelques principes:
- Si un noeud a un enfant droit,Pas de gauche.,Ce n'est pas un arbre binaire complet;
- La première fois que j'ai rencontré un enfant de gauche et de droite qui n'était pas double,Les noeuds restants doivent être des noeuds foliaires,Sinon, ce n'est pas un arbre binaire complet.
La routine récursive
Objectifs:X Si l'arbre binaire avec la tête est un arbre binaire complet;
Possibilité:Classification——Où est le dernier noeud du dernier étage
① Le noeud de la dernière couche est plein:Si l'arbre gauche est plein,L'arbre droit est aussi plein,Et les arbres de gauche et de droite ont la même hauteur,Par X Cet arbre binaire à la tête doit être un arbre binaire complet.(L'arbre gauche est plein,L'arbre droit est plein,Hauteur gauche = Hauteur droite)
②Noeud de dernière couche insatisfait:
1) Le dernier noeud est dans l'arbre de gauche,Mais l'arbre gauche n'est pas plein:Si l'arbre de gauche est un arbre binaire complet,Et l'arbre droit est plein,Et l'arbre gauche est plus grand que l'arbre droit1,Alors X Cet arbre binaire à la tête doit être un arbre binaire complet.(À gauche,Plein à droite,Hauteur gauche = Hauteur droite + 1)
2)Le dernier noeud fait que l'arbre gauche est plein:L'arbre gauche est plein,L'arbre droit est plein,La hauteur de l'arbre gauche est plus grande que celle de l'arbre droit1,Alors X Cet arbre binaire à la tête doit être un arbre binaire complet.(Gauche.,Plein à droite,Hauteur gauche = Hauteur droite+ 1)
3)Le dernier noeud est dans l'arbre de droite,Mais l'arbre droit n'est pas plein:L'arbre gauche est plein,L'arbre droit est un arbre binaire complet,Et les arbres de gauche et de droite ont la même hauteur,Alors X Cet arbre binaire à la tête doit être un arbre binaire complet.(Gauche., Droite. ,Hauteur gauche = Hauteur droite)Pour soutenir 4 Possibilité de semences, Informations à recueillir auprès des arbres de gauche et de droite :(1)Est un arbre binaire complet;(2)Si c'est un arbre binaire complet;(3)Hauteur.
3、Réalisation
C++ Édition
/************************************************************************* > File Name: 041.Déterminer si un arbre binaire est un arbre binaire complet.cpp > Author: Maureen > Mail: [email protected] > Created Time: Un. 7/ 4 19:39:10 2022 ************************************************************************/
#include <iostream>
#include <ctime>
#include <queue>
using namespace std;
class TreeNode {
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int data) : value(data) {
}
};
//Méthode 1:Pratique classique
bool isCBT1(TreeNode *root) {
if (root == nullptr) return true;
queue<TreeNode*> _que;
bool leaf = true;
TreeNode *l = nullptr;
TreeNode *r = nullptr;
_que.push(root);
while (!_que.empty()) {
root = que.front();
que.pop();
l = root->left;
r = root->right;
// Un noeud incomplet a été rencontré et le noeud courant n'est pas un noeud foliaire Ou Avoir un enfant droit sans enfant gauche
if (leaf && (l != nullptr || r != nullptr)) || (l == nullptr && r != nullptr) ) {
return false;
}
if (l != nullptr) {
_que.push(l);
}
if (r != nullptr) {
_que.push(r);
}
if (l == nullptr || r == nullptr) {
//Juste un enfant, C'est le cas d'un enfant incomplet
leaf = true;
}
}
return true;
}
//Méthode 2:La routine récursive de l'arbre binaire
class Info {
public:
bool isFull;
bool isCBT;
int height;
Info(bool full, bool cbt, int h) :
isFull(full), isCBT(cbt), height(h) {
}
};
Info *process(TreeNode *x) {
if (x == nullptr) {
retur new Info(true, true, 0);
}
Info *leftInfo = process(x->left);
Info *rightInfo = process(x->right);
int height = max(leftInfo->height, rightInfo->height) + 1;
bool isFull = leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height;
bool isCBT = false;
//Possibilité1:Gauche.,Plein à droite,Hauteur gauche = Hauteur droite
if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height) {
isCBT = true;
} else if (leftInfo->isCBT && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
//Possibilité2:À gauche,Plein à droite,Hauteur gauche = Hauteur droite + 1
isCBT = true;
} else if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
//Possibilité3:Gauche.,Plein à droite,Hauteur gauche = Hauteur droite + 1
isCBT = true;
} else if (leftInfo->isFull && right->isCBT && leftInfo->height == rightInfo->height) {
//Possibilité4:Gauche., Droite. ,Hauteur gauche = Hauteur droite
isCBT = true;
}
return new Info(isFull, isCBT, height);
}
bool isCBT2(TreeNode *root) {
return process(root)->isCBT;
}
//for test
TreeNode *generate(int level, int maxl, int maxv) {
if (level > maxl || (rand() % 100 / (double)101) < 0.5)
return nullptr;
TreeNode *root = new TreeNode(rand() % maxv);
root->left = generate(level + 1, maxl, maxv);
root->right = generate(level + 1, maxl, maxv);
return root;
}
TreeNode *generateRandomBST(int level, int value) {
return generate(1, level, value);
}
int main() {
srand(time(0));
int maxLevel = 4;
int maxValue = 100;
int testTimes = 1000001;
cout << "Test begin:" << endl;
for (int i = 0; i < testTimes; i++) {
TreeNode *root = generateRandomBST(maxLevel, maxValue);
if (isCBT1(root) != isCBT2(root)) {
cout << "Failed!" << endl;
return 0;
}
if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
}
cout << "Success!!" << endl;
return 0;
}
Java Édition
import java.util.LinkedList;
public class IsCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
//Pratique classique
public static boolean isCBT1(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
// Avez - vous déjà rencontré un noeud où les enfants de gauche et de droite ne sont pas tous les deux
boolean leaf = false;
Node l = null;
Node r = null;
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if (
// Si vous rencontrez un noeud incomplet,Le noeud actuel n'est pas un noeud foliaire
(leaf && (l != null || r != null))
||
(l == null && r != null) // Il y a des cas de droite ou de gauche
) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
}
if (l == null || r == null) {
// S'il n'y a qu'un seul enfant ou s'il n'y a pas d'enfant , C'est la situation où les enfants ne sont pas parfaits
leaf = true;
}
}
return true;
}
// La pratique des routines récursives
public static boolean isCBT2(Node head) {
return process(head).isCBT;
}
public static class Info {
public boolean isFull; // Plein ou pas
public boolean isCBT;// Si l'arbre binaire complet
public int height; //Hauteur
public Info(boolean full, boolean cbt, int h) {
isFull = full;
isCBT = cbt;
height = h;
}
}
public static Info process(Node x) {
if (x == null) {
// Configuration de l'arbre vide
return new Info(true, true, 0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// Les arbres à gauche et à droite sont pleins , Et la hauteur est constante ,C'est plein d'arbres binaires
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
boolean isCBT = false;
//Possibilité1: Les arbres à gauche et à droite sont pleins , Et la hauteur est constante
if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
isCBT = true;
}
//Possibilité2: L'arbre de gauche est complètement ,L'arbre droit est plein, L'arbre de gauche est plus haut que l'arbre de droite 1
else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
//Possibilité3:L'arbre gauche est plein,L'arbre droit est plein, L'arbre de gauche est plus haut que l'arbre de droite 1
else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
//Possibilité4:L'arbre gauche est plein, Le nombre de droite est , Les arbres de gauche et de droite ont la même hauteur
else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
isCBT = true;
}
return new Info(isFull, isCBT, height);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isCBT1(head) != isCBT2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
边栏推荐
- Global and Chinese markets for children's amusement facilities 2022-2028: Research Report on technology, participants, trends, market size and share
- Overview of Fourier analysis
- 抖音__ac_signature
- First, redis summarizes the installation types
- 分布式解决方案选型
- 利用LNMP实现wordpress站点搭建
- Usage Summary of scriptable object in unity
- audiopolicy
- Data type, variable declaration, global variable and i/o mapping of PLC programming basis (CoDeSys)
- The difference between MVVM and MVC
猜你喜欢
链表之双指针(快慢指针,先后指针,首尾指针)
PLC编程基础之数据类型、变量声明、全局变量和I/O映射(CODESYS篇 )
Commonly used probability distributions: Bernoulli distribution, binomial distribution, polynomial distribution, Gaussian distribution, exponential distribution, Laplace distribution and Dirac delta d
数据库基础知识(面试)
Unity Max and min constraint adjustment
Common JVM tools and optimization strategies
How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
MoCo: Momentum Contrast for Unsupervised Visual Representation Learning
Registration and skills of hoisting machinery command examination in 2022
Lesson 1: serpentine matrix
随机推荐
[untitled]
Simple and beautiful method of PPT color matching
一文搞定垃圾回收器
【Note17】PECI(Platform Environment Control Interface)
Nanjing: full use of electronic contracts for commercial housing sales
Hcip day 11 (BGP agreement)
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
openresty ngx_lua请求响应
Usage Summary of scriptable object in unity
Element operation and element waiting in Web Automation
Overview of Fourier analysis
Function default parameters, function placeholder parameters, function overloading and precautions
C Primer Plus Chapter 9 question 10 binary conversion
Editor extensions in unity
Global and Chinese markets for welding products 2022-2028: Research Report on technology, participants, trends, market size and share
Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
Using LNMP to build WordPress sites
Global and Chinese markets of tantalum heat exchangers 2022-2028: Research Report on technology, participants, trends, market size and share
Ieventsystemhandler event interface
Global and Chinese market of diesel fire pump 2022-2028: Research Report on technology, participants, trends, market size and share