Le concept d'arbre binaire
Un arbre binaire est un ensemble fini de nœuds n (n> = 0). Cet ensemble est soit un ensemble vide (arbre binaire vide), soit se compose d'un nœud racine et de deux arbres binaires qui ne se croisent pas, appelés nœuds racine et sous-arbre droit respectivement.
Caractéristiques des arbres binaires
Chaque nœud a au plus deux sous-sous-sous, il n'y a donc pas de nœuds avec un degré supérieur à 2 dans l'arbre binaire. Chaque nœud de l'arbre binaire est un objet, et chaque nœud de données a trois pointeurs, à savoir les pointeurs vers le parent, l'enfant gauche et l'enfant droit. Chaque nœud est connecté les uns aux autres via un pointeur. La relation entre les pointeurs connectés est toute la relation père-fils.
Définition des nœuds d'arbres binaires
Le nœud d'arbre binaire est défini comme suit:
La copie de code est la suivante:
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 à la fois un sous-arbre à gauche et à droite
Il n'y a que deux cas pour les arbres ordinaires avec trois nœuds: deux ou trois. Cependant, comme l'arbre binaire doit distinguer la gauche et la droite, elle évoluera vers les cinq formes suivantes:
Arbre binaire spécial
Arbre incliné
Comme indiqué dans les deuxième et troisième petites images de l'avant-dernière sous-picture 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 sur la même couche, un tel arbre binaire est appelé un arbre binaire complet. Comme indiqué dans la figure ci-dessous:
Arbre binaire complet
Un arbre complètement binaire signifie que la dernière couche est pleine à gauche, le côté droit peut être plein ou non, et le reste des couches est plein. Un arbre binaire avec une profondeur de K et un certain nombre de nœuds de 2 ^ k - 1 est un arbre binaire complet (arbre binaire complet). C'est un arbre avec une profondeur de K et pas d'espace.
Les caractéristiques d'un arbre complètement binaire sont:
Les nœuds de feuilles ne peuvent apparaître que dans les deux couches les plus basses.
La feuille la plus basse doit être concentrée en position continue à gauche.
Dans l'avant-dernière couche, s'il y a des nœuds de feuilles, ils doivent être en position continue à droite.
Si le degré de nœud est 1, le nœud n'a que l'enfant gauche.
Pour les arbres binaires avec le même nœud, l'arbre binaire complet a la plus petite profondeur.
Remarque: Un arbre binaire complet doit être un arbre complètement binaire, mais un arbre complètement binaire n'est peut-être pas un arbre binaire complet.
L'algorithme est le suivant:
La copie de code est la suivante:
bool is_complete (arbre * root)
{
file d'attente Q;
arbre * ptr;
/-
Q.push (racine);
while ((ptr = q.pop ())! = null)
{
q.push (ptr-> gauche);
q.push (ptr-> à droite);
}
// déterminer s'il y a encore des nœuds qui n'ont pas été accessibles
While (! Q.is_empty ())
{
ptr = q.pop ();
// S'il existe des nœuds non nuls qui ne sont pas accessibles, l'arbre a un vide et est un arbre binaire non complet.
if (null! = ptr)
{
retourne false;
}
}
Retour Vrai;
}
Propriétés des arbres binaires
Propriété 1 de l'arbre binaire: il y a au plus 2 ^ (i-1) nœuds sur la i-that de l'arbre binaire (i> = 1)
Propriété 2 de l'arbre binaire: arbre binaire avec la profondeur k a au plus 2 ^ k-1 nœuds (k> = 1)
Structure de stockage séquentielle des arbres binaires
La structure de stockage séquentielle d'un arbre binaire consiste à utiliser 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 des liens binaires
Étant donné que la méthode de stockage séquentielle n'est pas très applicable, nous devons considérer la structure de stockage de la chaîne. Selon la pratique internationale, le stockage des arbres binaires adopte généralement une structure de stockage de 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 cela. Nous appelons une telle liste liée une liste liée binaire.
Traversion des arbres binaires
Le traversant l'arbre binaire fait référence à l'accès à tous les nœuds de l'arbre binaire dans un certain ordre à partir du nœud racine, de sorte que chaque nœud est accessible une fois et une seule fois.
Il existe trois façons de traverser les arbres binaires, comme suit:
(1. Racine abrégée - gauche - droite.
(2) Traversion dans l'ordre (LDR), d'abord traverser le sous-arbre gauche, puis accéder au nœud racine et enfin traverser le sous-arbre droit. Remarque abrégée: ROT-ROOT-DIGMENT.
(3) Traversion post-ordre (LRD), traversant d'abord le sous-arbre gauche, puis traversant le sous-arbre droit et accédant enfin au nœud racine. Abrégé à gauche-droite.
Traversion préambule:
Si l'arbre binaire est vide, l'opération vide revient. Sinon, accédez d'abord au nœud racine, puis traversez le sous-arbre gauche dans l'ordre précédent, puis traversez le sous-arbre droit dans l'ordre précédent.
L'ordre de traversée est: Abdhiejcfkg
La copie de code est la suivante:
// Traversement précis
Fonction Précommande (node) {
if (! node == null) {
putstr (node.show () + "");
précommande (node.left);
précommande (Node.Right);
}
}
Traversion en ordre:
Si l'arborescence est vide, l'opération vide revient, sinon elle commence à partir du nœud racine (notez que le nœud racine n'est pas accessible en premier), et le sous-arbre gauche du nœud racine est traversé dans l'ordre moyen, alors le nœud racine est accessible, et enfin le sous-arbre droit est traversé dans l'ordre du milieu.
L'ordre de traversée est: hdibejafkcg
La copie de code est la suivante:
// Utiliser la méthode récursive pour implémenter une traversée d'ordre moyen
fonction inOrder (node) {
if (! (node == null)) {
inOrder (node.left); // Ajouter d'abord au sous-arbre gauche
putstr (node.show () + ""); // ajouter à nouveau au nœud racine
inOrder (node.right); // dernier accès au bon sous-arbre
}
}
Traversion post-ordre:
Si l'arbre est vide, l'opération vide revient. Sinon, les sous-arbres gauche et droit sont traversés de gauche à droite pour accéder aux sous-arbres gauche et droit, et enfin accéder au nœud racine.
L'ordre de traversée est: Hidjebkfgca
La copie de code est la suivante:
// Traversion post-ordre
Fonction postorder (nœud) {
if (! node == null) {
Postorder (Node.left);
Postorder (Node.Right);
putstr (node.show () + "");
}
}
Implémenter l'arbre de recherche binaire
L'arbre de recherche binaire (BST) est composé de nœuds, nous définissons donc un objet de nœud de nœud comme suit:
La copie de code est la suivante:
Node de fonction (données, gauche, droite) {
this.data = data;
this.left = gauche; // Enregistrer le lien de nœud gauche
this.Right = droite;
this.show = show;
}
fonction show () {
Renvoie ce.data; // afficher les données enregistrées dans le nœud
}
Trouver des valeurs maximales et minimales
Trouver les valeurs minimales et maximales sur le BST est très simple, car les valeurs plus petites sont toujours sur le nœud enfant gauche et à la recherche de la valeur minimale sur le BST, il suffit de traverser l'arbre enfant gauche jusqu'à ce que le dernier nœud soit trouvé
Trouvez la valeur minimale
La copie de code est la suivante:
fonction getmin () {
var courant = this.root;
while (! (current.left == null)) {
courant = courant.left;
}
retour current.data;
}
Cette méthode traverse une par une le long du sous-arbre gauche de BST jusqu'à ce qu'elle traverse le nœud le plus à gauche de BST, qui est défini comme:
La copie de code est la suivante:
current.left = null;
À l'heure actuelle, la valeur enregistrée sur le nœud actuel est la valeur minimale
Trouver la valeur maximale
La recherche de la valeur maximale sur BST nécessite uniquement la traversée du 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.
La copie de code est la suivante:
fonction getMax () {
var courant = this.root;
while (! (current.right == null)) {
courant = courant.Right;
}
retour current.data;
}