Explication détaillée de l'arbre binaire des structures de données et des algorithmes JavaScript_Connaissances de base

Le concept d'arbre binaire

L'arbre binaire est un ensemble fini de n (n>=0) nœuds. L'ensemble est soit un ensemble vide (arbre binaire vide), soit il se compose d'un nœud racine et de deux arbres mutuellement disjoints. composé du sous-arbre gauche et du sous-arbre droit du nœud racine.

Caractéristiques des arbres binaires

Chaque nœud a au plus deux sous-arbres, il n'y a donc aucun nœud avec un degré supérieur à 2 dans l'arbre binaire. Chaque nœud de l'arborescence binaire est un objet et chaque nœud de données possède trois pointeurs, qui sont des pointeurs vers le parent, l'enfant de gauche et l'enfant de droite. Chaque nœud est connecté les uns aux autres via des pointeurs. La relation entre les pointeurs connectés est une relation parent-enfant.

Définition du nœud d'arbre binaire

Les nœuds de l'arbre binaire sont définis comme suit :

Copier le code Le code est le suivant :

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

Cinq formes de base d'arbres binaires

Arbre binaire vide
Il n'y a qu'un seul nœud racine
Le nœud racine n'a que le sous-arbre gauche
Le nœud racine n'a que le bon sous-arbre
Le nœud racine a des sous-arbres gauche et droit

Il n'y a que deux situations pour un arbre ordinaire à trois nœuds : deux couches ou trois couches. Mais comme l'arbre binaire doit distinguer la gauche et la droite, il évoluera vers les cinq formes suivantes :

Arbre binaire spécial

Arbre incliné

Comme le montrent les 2ème et 3ème images de la dernière photo ci-dessus.

Arbre binaire complet

Dans un arbre binaire, si tous les nœuds de branche ont des sous-arbres gauche et droit, et que toutes les feuilles sont au même niveau, un tel arbre binaire est appelé un arbre binaire complet. Comme indiqué ci-dessous :

Arbre binaire complet

Un arbre binaire complet signifie que le côté gauche du dernier niveau est plein, le côté droit peut être plein ou non, puis les niveaux restants sont pleins. Un arbre binaire de profondeur k et de nombre de nœuds 2 ^ k - 1 est un arbre binaire complet (arbre binaire complet). C'est un arbre de profondeur k et sans trou.

Les caractéristiques d'un arbre binaire complet sont :

Les nœuds feuilles ne peuvent apparaître que sur les deux niveaux inférieurs.

Les feuilles les plus basses doivent être concentrées sur la position continue gauche.

Sur l'avant-dernière couche, s'il y a des nœuds feuilles, ils doivent être dans des positions continues à droite.

Si le degré du nœud est 1, alors le nœud n'a laissé qu'un enfant.

Un arbre binaire avec le même arbre de nœuds, un arbre binaire complet a la plus petite profondeur.

Remarque : un arbre binaire complet doit être un arbre binaire complet, mais un arbre binaire complet n'est pas nécessairement un arbre binaire complet.

L'algorithme est le suivant :

Copier le code Le code est le suivant :

bool is_complete(arbre *racine)
{
file d'attente q
arbre *ptr
// Effectue un parcours en largeur (traversée de niveau) et met les nœuds NULL dans la file d'attente
q.push(racine);
Tandis que ((ptr = q.pop()) != NULL)
{ 
           q.push(ptr->gauche);             q.push(ptr->right);  }  

// Détermine s'il existe des nœuds non visités Tandis que (!q.is_empty())

{ 
ptr = q.pop();

// S'il y a des nœuds non NULL non visités, l'arbre a des trous et est un arbre binaire non complet

Si (NULL != ptr)

                                                                                                  return false ;                                                                                                                                                }  

renvoie vrai ;
}

Propriétés des arbres binaires

Propriété 1 d'un arbre binaire : Il y a au plus 2^(i-1) nœuds (i>=1) au i-ème niveau de l'arbre binaire

Propriété 2 des arbres binaires : Un arbre binaire de profondeur k a au plus 2^k-1 nœuds (k>=1)

Structure de stockage séquentielle de l'arbre binaire

La structure de stockage séquentielle d'un arbre binaire utilise un tableau unidimensionnel pour stocker chaque nœud dans l'arbre binaire, et l'emplacement de stockage des nœuds peut refléter la relation logique entre les nœuds.

Liste chaînée binaire

Étant donné que l'applicabilité du stockage séquentiel n'est pas forte, nous devons considérer la structure de stockage en chaîne. Selon la pratique internationale, le stockage des arbres binaires utilise généralement une structure de stockage en chaîne.

Chaque nœud d'un arbre binaire a au plus deux enfants, c'est donc une idée naturelle de concevoir un champ de données et deux champs de pointeur pour celui-ci. Nous appelons une telle liste chaînée une liste chaînée binaire.

Parcours d'arbre binaire

Parcourir un arbre binaire signifie partir du nœud racine et visiter tous les nœuds de l'arbre binaire dans un certain ordre afin que chaque nœud soit visité une et une seule fois.

Il existe trois façons de parcourir un arbre binaire, comme suit :

(1) Traversée de précommande (DLR), visitez d'abord le nœud racine, puis traversez le sous-arbre de gauche et enfin traversez le sous-arbre de droite. L'abréviation racine-gauche-droite.

(2) Le parcours dans l'ordre (LDR), traverse d'abord le sous-arbre de gauche, puis visite le nœud racine et traverse enfin le sous-arbre de droite. Abrégé en gauche-racine-droite.

(3) Le parcours post-ordre (LRD), traverse d'abord le sous-arbre gauche, puis traverse le sous-arbre droit et visite enfin le nœud racine. Abrégé en racine gauche-droite.

Parcours des précommandes :

Si l'arbre binaire est vide, aucune opération n'est renvoyée, sinon le nœud racine est visité en premier, puis le sous-arbre de gauche est parcouru en pré-ordre, puis le sous-arbre de droite est parcouru en pré-ordre.

L'ordre de parcours est : A B D H I E J C F K G

Copier le code Le code est le suivant :

//Parcours des précommandes
fonction preOrder(nœud){
Si(!node == null){
          putstr(node.show() " ");
          preOrder(node.left);
          preOrder(node.right);
>
>

Parcours dans l'ordre :

Si l'arbre est vide, aucune opération ne revient, sinon en partant du nœud racine (notez que le nœud racine n'est pas visité en premier), parcourez le sous-arbre gauche du nœud racine dans l'ordre, puis visitez le nœud racine, et enfin Parcourez le sous-arbre de droite dans l'ordre.

L'ordre de parcours est : H D I B E J A F K C G

Copier le code Le code est le suivant :

//Utiliser la récursivité pour implémenter le parcours dans l'ordre
fonction dansOrdre(nœud){
Si(!(noeud ​​== null)){
inOrder(node.left);//Visitez d'abord le sous-arbre de gauche
           putstr(node.show() " ");//Visitez à nouveau le nœud racine
inOrder(node.right);//Dernier accès au sous-arbre de droite
>
>

Parcours post-commande :

Si l'arbre est vide, l'opération sans opération revient, sinon les sous-arbres gauche et droit sont parcourus de gauche à droite, d'abord les feuilles puis les nœuds, et enfin le nœud racine est visité.

L'ordre de parcours est : H I D J E B K F G C A

Copier le code Le code est le suivant :

//Parcours post-commande
fonction postOrder(noeud){
Si(!node == null){
PostOrder(node.left);
         postOrder(node.right);
           putStr(node.show() " ");
>
>

Implémenter un arbre de recherche binaire

L'arbre de recherche binaire (BST) est composé de nœuds, nous définissons donc un objet nœud Node comme suit :

Copier le code Le code est le suivant :

fonction Noeud (données, gauche, droite) {
This.data = data;
This.left = left;//Enregistrez le lien du nœud gauche
This.right = droite;
This.show = show;
>

fonction show(){
Renvoie this.data;//Affiche les données enregistrées dans le nœud
>

Trouver les valeurs maximales et minimales

Trouver les valeurs minimales et maximales sur un BST est très simple car la plus petite valeur est toujours sur le nœud enfant de gauche. Pour trouver la valeur minimale sur un BST, parcourez simplement le sous-arbre de gauche jusqu'à ce que le dernier nœud soit trouvé. 🎜>

Trouver la valeur minimale

Copier le code Le code est le suivant :

fonction getMin(){
var courant = this.root;
Tandis que(!(current.left == null)){
Actuel = actuel.gauche;
>
Renvoie current.data;
>

Cette méthode parcourt le sous-arbre gauche du BST un par un jusqu'à atteindre le nœud le plus à gauche du BST, qui est défini comme :

Copier le code Le code est le suivant :

current.left = null;

A ce moment, la valeur enregistrée sur le nœud actuel est la valeur minimale

Trouver la valeur maximale

Trouver la valeur maximale sur BST nécessite uniquement de parcourir le sous-arbre droit jusqu'à ce que le dernier nœud soit trouvé, et la valeur enregistrée sur ce nœud est la valeur maximale.

Copier le code Le code est le suivant :

fonction getMax(){
var courant = this.root;
Tandis que(!(current.right == null)){
            current = current.right;
>
Renvoie current.data;
>