Déterminer si un arbre binaire est un arbre binaire complet

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

1. Objectifs：X Si l'arbre binaire avec la tête est un arbre binaire complet;

2. 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）

3. 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!");
	}
}