Arbre binaire en C
En C, un arbre binaire est une instance d'une structure de données arborescente avec un nœud parent qui peut posséder un nombre maximum de deux nœuds enfants ; 0, 1 ou 2 nœuds descendants. Chaque nœud unique dans un arbre binaire a une valeur qui lui est propre et deux pointeurs vers ses enfants, un pointeur pour l'enfant gauche et l'autre pour l'enfant droit.
Déclaration d'arbre binaire
UN arbre binaire peut être déclaré en C à l'aide d'un objet appelé structure qui représente l'un des nœuds de l'arbre.
structure nœud {
type de données var_name ;
structure nœud * gauche ;
structure nœud * droite ;
} ;
Ci-dessus est une déclaration d'un arbre binaire nom du nœud en tant que nœud. Il contient trois valeurs; l'un est la variable de stockage de données et les deux autres sont les pointeurs vers l'enfant. (enfant gauche et droit du nœud parent).
Faits de l'arbre binaire
Même pour de grands ensembles de données, l'utilisation d'un arbre binaire rend la recherche plus facile et plus rapide. Le nombre de branches d'arbre n'est pas limité. Contrairement à un tableau, des arbres de toutes sortes peuvent être créés et agrandis en fonction de ce qui est requis d'un individu.
Implémentation de l'arbre binaire en C
Ce qui suit est un guide étape par étape pour la mise en œuvre d'un Arbre binaire en C
Étape 1 : déclarer un arbre de recherche binaire
Créez un nœud struct qui a trois types de données, tels que data, *left_child et *right_child, où les données peuvent être de type entier, et les nœuds *left_child et *right_child peuvent être déclarés comme NULL ou non.
structure nœud{
entier données ;
structure nœud * droit_enfant ;
structure nœud * enfant_gauche ;
} ;
Étape 2 : Créer de nouveaux nœuds dans l'arborescence de recherche binaire
Créez un nouveau nœud en créant une fonction qui accepte un entier comme argument et fournit le pointeur vers le nouveau nœud créé avec cette valeur. Utilisez la fonction malloc() en C pour l'allocation dynamique de mémoire pour le nœud créé. Initialisez les enfants gauche et droit à NULL et renvoyez le nodeName.
structure nœud * créer ( données de type de données )
{
structure nœud * nodeName = malloc ( taille de ( structure nœud ) ) ;
nodeName -> données = valeur ;
nodeName -> enfant_gauche = nodeName -> droit_enfant = NUL ;
retour nodeName ;
}
Étape 3 : Insérer les enfants droit et gauche dans l'arborescence binaire
Créez des fonctions insert_left et insert_right qui accepteront deux entrées, qui sont la valeur à insérer et le pointeur vers le nœud auquel les deux enfants seront connectés. Appelez la fonction create pour créer un nouveau nœud et affectez le pointeur renvoyé au pointeur gauche de l'enfant gauche ou au pointeur droit de l'enfant droit du parent racine.
structure nœud * insert_left ( structure nœud * racine , données de type de données ) {racine -> gauche = créer ( données ) ;
retour racine -> gauche ;
}
structure nœud * insert_right ( structure nœud * racine , données de type de données ) {
racine -> droite = créer ( données ) ;
retour racine -> droite ;
}
Étape 4 : Afficher les nœuds de l'arborescence binaire à l'aide des méthodes de traversée
Nous pouvons afficher des arbres en utilisant trois méthodes de parcours en C. Ces méthodes de parcours sont :
1 : Traversée de la précommande
Dans cette méthode de parcours, nous allons parcourir les nœuds dans une direction allant de parent_node->left_child->right_child .
annuler Pré-commander ( nœud * racine ) {si ( racine ) {
printf ( '%d \n ' , racine -> données ) ;
display_pre_order ( racine -> gauche ) ;
display_pre_order ( racine -> droite ) ;
}
}
2 : Traversée post-commande
Dans cette méthode de parcours, nous allons passer par les nœuds dans une direction allant du enfant_gauche->enfant_droit->nœud_parent-> .
annuler display_post_order ( nœud * racine ) {si ( arbre_binaire ) {
display_post_order ( racine -> gauche ) ;
display_post_order ( racine -> droite ) ;
printf ( '%d \n ' , racine -> données ) ;
}
}
3 : Traversée dans l'ordre
Dans cette méthode de parcours, nous allons parcourir les nœuds dans une direction allant de nœud_gauche->enfant_racine->enfant_droit .
annuler display_in_order ( nœud * racine ) {si ( arbre_binaire ) {
display_in_order ( racine -> gauche ) ;
printf ( '%d \n ' , racine -> données ) ;
display_in_order ( racine -> droite ) ;
}
}
Étape 5 : Effectuez la suppression dans l'arborescence binaire
Nous pouvons supprimer le créé Arbre binaire en supprimant les deux enfants avec la fonction de nœud parent en C comme suit.
annuler delete_t ( nœud * racine ) {si ( racine ) {
delete_t ( racine -> gauche ) ;
delete_t ( racine -> droite ) ;
gratuit ( racine ) ;
}
}
Programme C de l'arbre de recherche binaire
Voici l'implémentation complète de l'arborescence de recherche binaire en programmation C :
#include#include
structure nœud {
entier valeur ;
structure nœud * gauche , * droite ;
} ;
structure nœud * noeud1 ( entier données ) {
structure nœud * tmp = ( structure nœud * ) malloc ( taille de ( structure nœud ) ) ;
tmp -> valeur = données ;
tmp -> gauche = tmp -> droite = NUL ;
retour tmp ;
}
annuler imprimer ( structure nœud * Noeud principal ) // affichage des nœuds !
{
si ( Noeud principal != NUL ) {
imprimer ( Noeud principal -> gauche ) ;
printf ( '%d \n ' , Noeud principal -> valeur ) ;
imprimer ( Noeud principal -> droite ) ;
}
}
structure nœud * insert_node ( structure nœud * nœud , entier données ) // insertion de nœuds !
{
si ( nœud == NUL ) retour noeud1 ( données ) ;
si ( données < nœud -> valeur ) {
nœud -> gauche = insert_node ( nœud -> gauche , données ) ;
} autre si ( données > nœud -> valeur ) {
nœud -> droite = insert_node ( nœud -> droite , données ) ;
}
retour nœud ;
}
entier principal ( ) {
printf ( 'Implémentation en C de l'arbre de recherche binaire ! \n \n ' ) ;
structure nœud * parent = NUL ;
parent = insert_node ( parent , dix ) ;
insert_node ( parent , 4 ) ;
insert_node ( parent , 66 ) ;
insert_node ( parent , Quatre cinq ) ;
insert_node ( parent , 9 ) ;
insert_node ( parent , 7 ) ;
imprimer ( parent ) ;
retour 0 ;
}
Dans le code ci-dessus, nous déclarons d'abord un nœud en utilisant structure . Ensuite, nous initialisons un nouveau nœud comme ' noeud1 ” et allouer dynamiquement de la mémoire en utilisant malloc() en C avec des données et deux pointeurs de type enfants en utilisant le nœud déclaré. Après cela, nous affichons le nœud par printf() fonction et appelez-la dans le principal() fonction. Puis le insertion_node() la fonction est créée, où si les données du nœud sont NULL alors noeud1 est retiré, sinon les données sont placées dans le nœud (parent) de l'enfant gauche et droit. Le programme commence son exécution à partir du principal() fonction, qui génère un nœud en utilisant quelques exemples de nœuds comme enfants, puis utilise des méthodes de parcours dans l'ordre pour imprimer le contenu du nœud.
Sortir
Conclusion
Les arbres sont fréquemment utilisés pour conserver les données sous une forme non linéaire. Arbres binaires sont des types d'arbres où chaque nœud (parent) a deux descendants, l'enfant gauche et l'enfant droit. UN arbre binaire est une méthode polyvalente de transfert et de stockage de données. Il est plus efficace que Linked-List en C. Dans l'article ci-dessus, nous avons vu le concept d'un Arbre binaire avec la mise en place progressive d'un Arbre de recherche binaire en C