binary tree data structure c
Ce didacticiel détaillé sur l'arborescence binaire en C ++ explique les types, la représentation, la traversée, les applications et l'implémentation des arbres binaires en C ++:
Un arbre binaire est une structure de données arborescente largement utilisée. Lorsque chaque nœud d'un arbre a au plus deux nœuds enfants, alors l'arbre est appelé un arbre binaire.
Ainsi, un arbre binaire typique aura les composants suivants:
- Un sous-arbre gauche
- Un nœud racine
- Un bon sous-arbre
=> Regardez la liste complète des didacticiels C ++ de cette série.
Ce que vous apprendrez:
- Arbre binaire en C ++
- Types d'arbre binaire
- Représentation d'arbre binaire
- Implémentation d'arbre binaire en C ++
- Traversée d'arbre binaire
- Applications de l'arbre binaire
- Conclusion
- lecture recommandée
Arbre binaire en C ++
Une représentation graphique d'un arbre binaire est présentée ci-dessous:
Dans un arbre binaire donné, le nombre maximum de nœuds à n'importe quel niveau est de 2l-1où «l» est le numéro du niveau.
Ainsi dans le cas du nœud racine au niveau 1, le nombre maximum de nœuds = 21-1= 20= 1
Comme chaque nœud dans un arbre binaire a au plus deux nœuds, le maximum de nœuds au niveau suivant sera, 2 * 2l-1.
test des performances des services Web à l'aide de loadrunner
Étant donné un arbre binaire de profondeur ou de hauteur de h, le nombre maximum de nœuds dans un arbre binaire de hauteur h = 2h- 1.
Donc dans un arbre binaire de hauteur 3 (illustré ci-dessus), le nombre maximum de nœuds = 23-1 = 7.
Voyons maintenant les différents types d'arbres binaires.
Types d'arbre binaire
Voici les types d'arbres binaires les plus courants.
# 1) Arbre binaire complet
Un arbre binaire dans lequel chaque nœud a 0 ou 2 enfants est appelé arbre binaire complet.
Ci-dessus, un arbre binaire complet dans lequel nous pouvons voir que tous ses nœuds à l'exception des nœuds feuilles ont deux enfants. Si L est le nombre de nœuds feuilles et «l» est le nombre de nœuds internes ou non-feuilles, alors pour un arbre binaire complet, L = l + 1.
# 2) Arbre binaire complet
Un arbre binaire complet a tous les niveaux remplis sauf pour le dernier niveau et le dernier niveau a tous ses nœuds autant que vers la gauche.
L'arbre illustré ci-dessus est un arbre binaire complet. Un exemple typique d'arbre binaire complet est un tas binaire dont nous parlerons dans les didacticiels ultérieurs.
# 3) Arbre binaire parfait
Un arbre binaire est qualifié de parfait lorsque tous ses nœuds internes ont deux enfants et que tous les nœuds feuilles sont au même niveau.
Un exemple d'arbre binaire montré ci-dessus est un arbre binaire parfait car chacun de ses nœuds a deux enfants et tous les nœuds feuilles sont au même niveau.
Un arbre binaire parfait de hauteur h a 2h- 1 nombre de nœuds.
# 4) Un arbre dégénéré
Un arbre binaire où chaque nœud interne n'a qu'un seul enfant est appelé un arbre dégénéré.
L'arbre illustré ci-dessus est un arbre dégénéré. En ce qui concerne les performances de cet arbre, les arbres dégénérés sont les mêmes que les listes chaînées.
# 5) Arbre binaire équilibré
Un arbre binaire dans lequel la profondeur des deux sous-arbres de chaque nœud ne diffère jamais de plus de 1 est appelé un arbre binaire équilibré.
L'arbre binaire montré ci-dessus est un arbre binaire équilibré car la profondeur des deux sous-arbres de chaque nœud n'est pas supérieure à 1. Les arbres AVL dont nous allons discuter dans nos tutoriels suivants sont un arbre équilibré commun.
Représentation d'arbre binaire
Un arbre binaire se voit allouer de la mémoire de deux manières.
# 1) Représentation séquentielle
Il s'agit de la technique la plus simple pour stocker une structure de données arborescente. Un tableau est utilisé pour stocker les nœuds de l'arborescence. Le nombre de nœuds dans une arborescence définit la taille du tableau. Le nœud racine de l'arborescence est stocké au premier index du tableau.
entreprises impliquées dans l'internet des objets
En général, si un nœud est stocké au iel'emplacement, puis l'enfant gauche et droit est stocké respectivement aux emplacements 2i et 2i + 1.
Considérez l'arbre binaire suivant.
La représentation séquentielle de l'arbre binaire ci-dessus est la suivante:
Dans la représentation ci-dessus, nous voyons que les enfants gauche et droit de chaque nœud sont stockés aux emplacements 2 * (node_location) et 2 * (node_location) +1 respectivement.
Par exemple, l'emplacement du nœud 3 dans le tableau est 3. Donc, son enfant de gauche sera placé à 2 * 3 = 6. Son enfant de droite sera à l'emplacement 2 * 3 +1 = 7. Comme nous pouvons le voir dans le tableau, les enfants de 3 qui sont 6 et 7 sont placés aux emplacements 6 et 7 dans le réseau.
La représentation séquentielle de l'arborescence est inefficace car le tableau utilisé pour stocker les nœuds de l'arborescence prend beaucoup d'espace en mémoire. À mesure que l'arbre grandit, cette représentation devient inefficace et difficile à gérer.
Cet inconvénient est surmonté en stockant les nœuds d'arbre dans une liste chaînée. Notez que si l'arborescence est vide, le premier emplacement stockant le nœud racine sera défini sur 0.
# 2) Représentation de liste liée
Dans ce type de représentation, une liste chaînée est utilisée pour stocker les nœuds de l'arborescence. Plusieurs nœuds sont dispersés dans la mémoire dans des emplacements non contigus et les nœuds sont connectés en utilisant la relation parent-enfant comme un arbre.
Le diagramme suivant montre une représentation de liste liée pour un arbre.
Comme indiqué dans la représentation ci-dessus, chaque nœud de liste liée comporte trois composants:
- Pointeur gauche
- Partie données
- Pointeur droit
Le pointeur gauche a un pointeur vers l'enfant gauche du nœud; le pointeur droit a un pointeur vers l'enfant droit du nœud tandis que la partie données contient les données réelles du nœud. S'il n'y a pas d'enfants pour un nœud donné (nœud feuille), les pointeurs gauche et droit de ce nœud sont définis sur null, comme indiqué dans la figure ci-dessus.
Implémentation d'arbre binaire en C ++
Ensuite, nous développons un programme d'arbre binaire utilisant une représentation de liste chaînée en C ++. Nous utilisons une structure pour déclarer un seul nœud, puis en utilisant une classe, nous développons une liste chaînée de nœuds.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< Production:
Arbre binaire créé:
5 10 15 20 30 40 45
Traversée d'arbre binaire
Nous avons déjà discuté des traversées dans notre tutoriel de base sur les arbres. Dans cette section, implémentons un programme qui insère des nœuds dans l'arbre binaire et démontre également les trois traversées, c'est-à-dire inorder, preorder et postorder, pour un arbre binaire.
#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'< Production:
Traversée en ordre:
A B C D E F G
Traversée de la vente par correspondance:
G F E D C B A
Parcours de précommande:
A B C D E F G
Applications de l'arbre binaire
Un arbre binaire est utilisé dans de nombreuses applications pour stocker des données.
Certaines des applications importantes des arbres binaires sont énumérées ci-dessous:
- Arbres de recherche binaires: Les arbres binaires sont utilisés pour construire un arbre de recherche binaire qui est utilisé dans de nombreuses applications de recherche telles que des ensembles et des cartes dans de nombreuses bibliothèques de langues.
- Arbres de hachage: Utilisé pour vérifier les hachages principalement dans les applications de signature d'images spécialisées.
- Tas: Les tas sont utilisés pour implémenter des files d'attente prioritaires qui sont utilisées pour les routeurs, les processeurs de planification dans le système d'exploitation, etc.
- Codage Huffman: L'arbre de codage de Huffman est utilisé dans les algorithmes de compression (comme la compression d'image) ainsi que dans les applications cryptographiques.
- Arbre de syntaxe: Les compilateurs construisent souvent des arbres de syntaxe qui ne sont rien d'autre que des arbres binaires pour analyser les expressions utilisées dans le programme.
Conclusion
Les arbres binaires sont des structures de données largement utilisées dans l'industrie du logiciel. Les arbres binaires sont les arbres dont les nœuds ont au plus deux nœuds enfants. Nous avons vu différents types d'arbres binaires comme un arbre binaire complet, un arbre binaire complet, un arbre binaire parfait, un arbre binaire dégénéré, un arbre binaire équilibré, etc.
Les données d'arbre binaire peuvent également être parcourues à l'aide des techniques de traversée inorder, preorder et postorder que nous avons vues dans notre tutoriel précédent. En mémoire, un arbre binaire peut être représenté à l'aide d'une liste chaînée (mémoire non contiguë) ou de tableaux (représentation séquentielle).
La représentation de liste liée est plus efficace par rapport aux tableaux, car les tableaux prennent beaucoup d'espace.
=> Découvrez les meilleurs didacticiels de formation C ++ ici.
lecture recommandée
- Arborescence AVL et structure de données de tas en C ++
- Arborescence B et structure de données d'arbre B + en C ++
- Structure de données de file d'attente en C ++ avec illustration
- Empiler la structure de données en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste liée en C ++ avec illustration
- Introduction aux structures de données en C ++
- Structure de données de file d'attente prioritaire en C ++ avec illustration