Arbre de recherche binaire C ++

BST est une structure de données qui maintient les données dans une liste triée. Il est connu comme un arbre de recherche binaire car, dans l'arbre, chaque nœud a un maximum de deux enfants qui ne peut pas être augmenté. Ceci est connu comme un arbre de recherche car il est utilisé pour rechercher ou trouver un élément présent. Nous implémenterons ce phénomène dans la langue C ++.

Mise en œuvre

Dans une implémentation, la première étape consiste à utiliser une structure pour initialiser la clé de type entier et les nœuds latéraux gauche et droit. Ces nœuds sont définis en utilisant un pointeur variable, car ils enregistrent tous les deux les adresses des nœuds alternatifs. Après cela, nous fermons la structure.

Nous allons recommencer un nouveau nœud via une structure. Le paramètre de la fonction contiendra les données que nous souhaitons entrer dans le nœud.

nœud struct * newNode (int item)

Il créera une nouvelle température de nœud qui y stockera des données, et la taille de la mémoire sera allouée via Malloc (). Nous ajouterons la valeur de l'élément dans la partie clé du nœud. Tandis que les parties gauche et droite, qui sont déclarées précédemment dans la structure, sont déclarées maintenant nuls car c'est le premier nœud. La température sera retournée.

Une fonction avec le nom «inordre» est créée, et il acceptera le nœud racine dans le paramètre. Comme nous le savons, l'arbre contient trois parties principales: nœud, gauche et côtés droits de l'arbre. Nous utiliserons une staté if pour vérifier si la racine n'est pas nul. Ensuite, appelez la fonction et envoyez la partie gauche de la racine. Cela affichera la racine elle-même avec une flèche qui indiquera la direction du chemin dans l'arbre. Ensuite, pour traverser le droit, appelez la fonction inférieure avec le droit de la racine comme paramètre.

Inordre (root -> gauche)

C'est ainsi que la traversée inférieure est faite. Pour insérer un nouveau nœud dans l'arbre, nous utiliserons une fonction qui prendra un nœud et la clé comme valeurs de paramètre. Si l'arbre est déjà vide, le nouveau nœud sera retourné. Dans le deuxième cas, si l'arbre n'est pas vide, allez d'abord sur le côté droit et insérez un nouveau nœud ici. Pour l'insertion, nous utiliserons une déclaration IF-Else pour vérifier la commande de la clé. La nouvelle clé ira sur le côté gauche pour l'ordre croissant. Si la pièce qui vérifie la nouvelle clé est inférieure à la valeur présente dans le nœud déjà, entrez la touche à la partie gauche du nœud.

Node -> Left = insert (Node -> gauche, clé)

Alors que si la clé est plus grande, elle ira à la bonne partie.

Après l'insertion du nœud, nous vérifierons le nœud suivant ou le nœud qui est le successeur. Une fonction de la valeur min est créée qui créera un nouveau nœud avec un nom * Current. Ce nœud sera attribué par une valeur transmise comme argument à la fonction. Il trouvera d'abord le nœud d'angle ou la feuille de mode gauche sur le côté gauche de l'arbre. Nous utilisons une boucle de temps qui itère jusqu'à ce que la traversée du nœud soit terminée. En d'autres termes, la partie gauche du nœud actuel n'est pas nul.

Courant = courant -> gauche

Continuez à affecter le nœud actuel La valeur du courant suivant à l'intérieur de la boucle à gauche.

Notre arbre est traversé et organisé en ajoutant des feuilles des deux côtés. Chaque valeur sera insérée via l'appel de fonction fait à partir du programme principal. Maintenant, nous devons rechercher n'importe quel élément et le supprimerons une fois qu'il sera trouvé.

L'arbre en C ++ fonctionne sur le même phénomène que la liste liée. Nous appliquerons la recherche binaire sur l'arbre et effectuerons une opération de suppression pour supprimer un nœud ou une feuille de l'arbre. Une fonction du nœud de suppression est créée; il contiendra l'arbre et la valeur en tant que paramètres. Nous vérifierons d'abord que les arbres doivent avoir des valeurs à l'intérieur. Ainsi, le statement IF sera utilisé, et si la racine est nulle, cela signifie retourner la racine uniquement.

If (clé clé)

La clé que vous souhaitez supprimer est plus petite que le nœud racine. Ensuite, déplacez-vous vers le côté gauche et appelez la fonction de suppression avec la partie gauche de l'arbre, et la clé à supprimer.

Root -> Left = Deletenode (root -> Left, key);

Et il en va de même pour la partie else-if. Si la clé est supérieure à la touche de nœud, puis accédez au chemin droit, appelez la fonction de suppression. Passez la bonne partie de l'arbre et la clé pour qu'il devienne facile de trouver le nœud que vous souhaitez supprimer.

Maintenant, venant vers la partie d'autre, c'est applicable si le nœud est seul, n'a pas de feuille plus loin, ou n'a qu'un seul enfant devant. À l'intérieur de la partie d'autre, si une instruction sera utilisée qui vérifiera s'il n'y a pas de nœud sur le côté droit, ajoutez la valeur sur le côté droit du nœud au nouveau nœud temporaire, de la même manière pour le côté gauche.

Struct nœud * temp = root -> gauche;

Dans cette condition, libérez la racine. Cela supprimera la valeur de la racine.

Libre (racine);

Si un nœud contient deux feuilles avec, puis pour rechercher la valeur, nous utiliserons la fonction de valeur min et la bonne partie sera envoyée à la fonction.

Minvaluenode (root -> à droite);

Lorsque la valeur à supprimer est trouvée, nous le déclarerons la dernière partie de l'arbre afin qu'il puisse être supprimé facilement.

Root -> key = temp -> key;

Après avoir fait cela, supprimez le nœud,

Root -> right = delete nœud (node ​​-> droite, temp -> key);

Après avoir clôturé la fonction, nous déclarerons le programme principal ici. Le nœud racine sera défini comme nul initialement. À l'aide de l'appel de fonction insert (), nous utiliserons la racine et les données numériques dans le nœud.

Insérer (racine, 5);

La fonction inférieure est appelée pour la traversée de l'arbre.

Inordre (racine);

Ensuite, pour supprimer le nœud, nous appellerons la fonction de suppression.

Root = deletenode (root, 10);

Après la suppression, les valeurs sont à nouveau affichées.

Après avoir écrit le code, nous l'exécuterons dans le terminal d'Ubuntu via le compilateur.

fichier de fichier $ g ++ -o.c
$ ./déposer

Comme vous pouvez le voir, les sept éléments sont entrés dans le nœud. L'un est supprimé, et le reste sera affiché dans le même ordre qu'avant.

Conclusion

Un arbre de recherche binaire est utilisé pour stocker les valeurs sous la forme triée. Pour rechercher un nombre, tous les chiffres doivent être triés en premier dans l'ordre. Après cela, le numéro spécifié est fouillé en divisant l'arbre en deux parties, ce qui fait des sous-arbres. L'implémentation BST se fait dans le système Ubuntu en expliquant un exemple de manière élaborée. Nous espérons que vous avez trouvé cet article utile. Consultez les autres articles sur les conseils pour plus de conseils et de tutoriels.