L'arbre binaire signifie que le nœud peut avoir au maximum deux enfants. Ici, le nom binaire lui-même suggère que « deux » ; par conséquent, chaque nœud peut avoir 0, 1 ou 2 enfants.
Comprenons l'arbre binaire à travers un exemple.
L'arbre ci-dessus est un arbre binaire car chaque nœud contient au maximum deux enfants. La représentation logique de l’arbre ci-dessus est donnée ci-dessous :
Dans l'arborescence ci-dessus, le nœud 1 contient deux pointeurs, c'est-à-dire un pointeur gauche et droit pointant respectivement vers les nœuds gauche et droit. Le nœud 2 contient à la fois les nœuds (nœud gauche et droit) ; il comporte donc deux pointeurs (gauche et droite). Les nœuds 3, 5 et 6 sont les nœuds feuilles, donc tous ces nœuds contiennent NUL pointeur sur les parties gauche et droite.
Propriétés de l'arbre binaire
- A chaque niveau de i, le nombre maximum de nœuds est de 2je.
- La hauteur de l’arborescence est définie comme le chemin le plus long depuis le nœud racine jusqu’au nœud feuille. L'arbre représenté ci-dessus a une hauteur égale à 3. Par conséquent, le nombre maximum de nœuds à la hauteur 3 est égal à (1+2+4+8) = 15. En général, le nombre maximum de nœuds possibles à la hauteur h est (20+ 21+ 22+….2h) = 2h+1-1.
- Le nombre minimum de nœuds possibles à la hauteur h est égal à h+1 .
- Si le nombre de nœuds est minimum, alors la hauteur de l’arbre sera maximale. A l’inverse, si le nombre de nœuds est maximum, alors la hauteur de l’arbre sera minimale.
S'il y a « n » nombre de nœuds dans l'arborescence binaire.
La hauteur minimale peut être calculée comme suit :
Comme nous le savons,
n = 2h+1-1
n+1 = 2h+1
Prenant une bûche des deux côtés,
enregistrer2(n+1) = log2(2h+1)
exemple de en java
enregistrer2(n+1) = h+1
h = journal2(n+1) - 1
La hauteur maximale peut être calculée comme suit :
Comme nous le savons,
n = h+1
h = n-1
Types d'arbre binaire
Il existe quatre types d'arbre binaire :
1. Arbre binaire complet/approprié/strict
L’arbre binaire complet est également appelé arbre binaire strict. L'arbre ne peut être considéré comme un arbre binaire complet que si chaque nœud doit contenir soit 0, soit 2 enfants. L'arbre binaire complet peut également être défini comme l'arbre dans lequel chaque nœud doit contenir 2 enfants à l'exception des nœuds feuilles.
Regardons l'exemple simple de l'arbre binaire complet.
Dans l’arborescence ci-dessus, nous pouvons observer que chaque nœud contient soit zéro, soit deux enfants ; il s’agit donc d’un arbre binaire complet.
Propriétés de l'arbre binaire complet
chaîne de concaténation en Java
- Le nombre de nœuds feuilles est égal au nombre de nœuds internes plus 1. Dans l'exemple ci-dessus, le nombre de nœuds internes est de 5 ; par conséquent, le nombre de nœuds feuilles est égal à 6.
- Le nombre maximum de nœuds est le même que le nombre de nœuds dans l'arbre binaire, soit 2h+1-1.
- Le nombre minimum de nœuds dans l’arbre binaire complet est de 2*h-1.
- La hauteur minimale de l'arbre binaire complet est enregistrer2(n+1) - 1.
- La hauteur maximale de l’arbre binaire complet peut être calculée comme suit :
n= 2*h - 1
n+1 = 2*h
h = n+1/2
Arbre binaire complet
L'arbre binaire complet est un arbre dans lequel tous les nœuds sont complètement remplis sauf le dernier niveau. Au dernier niveau, tous les nœuds doivent être le plus à gauche possible. Dans un arbre binaire complet, les nœuds doivent être ajoutés par la gauche.
python enregistrer json dans un fichier
Créons un arbre binaire complet.
L'arbre ci-dessus est un arbre binaire complet car tous les nœuds sont complètement remplis et tous les nœuds du dernier niveau sont ajoutés en premier à gauche.
Propriétés de l'arbre binaire complet
- Le nombre maximum de nœuds dans un arbre binaire complet est de 2h+1- 1.
- Le nombre minimum de nœuds dans un arbre binaire complet est de 2h.
- La hauteur minimale d'un arbre binaire complet est enregistrer2(n+1) - 1.
- La hauteur maximale d'un arbre binaire complet est
Arbre binaire parfait
Un arbre est un arbre binaire parfait si tous les nœuds internes ont 2 enfants et que tous les nœuds feuilles sont au même niveau.
Regardons un exemple simple d'arbre binaire parfait.
L'arbre ci-dessous n'est pas un arbre binaire parfait car tous les nœuds feuilles ne sont pas au même niveau.
Remarque : Tous les arbres binaires parfaits sont les arbres binaires complets ainsi que l'arbre binaire complet, mais l'inverse n'est pas vrai, c'est-à-dire que tous les arbres binaires complets et les arbres binaires complets sont les arbres binaires parfaits.
Arbre binaire dégénéré
L'arbre binaire dégénéré est un arbre dans lequel tous les nœuds internes n'ont qu'un seul enfant.
Comprenons l'arbre binaire dégénéré à travers des exemples.
L'arbre ci-dessus est un arbre binaire dégénéré car tous les nœuds n'ont qu'un seul enfant. Il est également connu sous le nom d’arbre asymétrique à droite, car tous les nœuds n’ont qu’un seul enfant droit.
L'arbre ci-dessus est également un arbre binaire dégénéré car tous les nœuds n'ont qu'un seul enfant. Il est également connu sous le nom d'arbre asymétrique à gauche, car tous les nœuds n'ont qu'un enfant gauche.
Arbre binaire équilibré
L'arbre binaire équilibré est un arbre dans lequel les arbres gauche et droit diffèrent d'au plus 1. Par exemple, AVL et Arbres rouge-noir sont des arbres binaires équilibrés.
Comprenons l'arbre binaire équilibré à travers des exemples.
L'arbre ci-dessus est un arbre binaire équilibré car la différence entre le sous-arbre gauche et le sous-arbre droit est nulle.
L'arbre ci-dessus n'est pas un arbre binaire équilibré car la différence entre le sous-arbre gauche et le sous-arbre droit est supérieure à 1.
Implémentation de l'arbre binaire
Un arbre binaire est implémenté à l'aide de pointeurs. Le premier nœud de l'arborescence est représenté par le pointeur racine. Chaque nœud de l'arborescence se compose de trois parties, à savoir les données, le pointeur gauche et le pointeur droit. Pour créer un arbre binaire, nous devons d’abord créer le nœud. Nous allons créer le nœud défini par l'utilisateur comme indiqué ci-dessous :
struct node { int data, struct node *left, *right; } Dans la structure ci-dessus, données est la valeur, pointeur gauche contient l'adresse du nœud gauche, et pointeur droit contient l'adresse du bon nœud.
jeux d'images pour Android
Programme d'arbre binaire en C
#include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } Le code ci-dessus appelle la fonction create() de manière récursive et crée un nouveau nœud à chaque appel récursif. Lorsque tous les nœuds sont créés, cela forme une structure arborescente binaire. Le processus de visite des nœuds est connu sous le nom de traversée d’arbre. Il existe trois types de parcours utilisés pour visiter un nœud :
- Parcours dans l'ordre
- Parcours des précommandes
- Traversée des mandats postaux