Qu’est-ce qu’un arbre binaire complet ?
Un arbre binaire complet peut être défini comme un arbre binaire dans lequel tous les nœuds ont 0 ou deux enfants. En d’autres termes, l’arbre binaire complet peut être défini comme un arbre binaire dans lequel tous les nœuds ont deux enfants à l’exception des nœuds feuilles.
L'arbre ci-dessous est un arbre binaire complet :
L'arbre ci-dessus est un arbre binaire complet car tous les nœuds, à l'exception des nœuds feuilles, ont deux enfants.
Théorème de l'arbre binaire complet :
objet java en json
Considérons un arbre binaire T comme un arbre non vide alors :
- Soit I des nœuds internes dans un arbre et L un nœud feuille dans un arbre, alors le nombre de nœuds feuilles serait égal à :
L = je + 1 - Si T a, I le nombre de nœuds internes et N le nombre total de nœuds, alors le nombre total de nœuds serait égal à :
N = 2I + 1 - Si T contient « N » le nombre total de nœuds et « I » le nombre de nœuds internes, alors le nombre de nœuds internes serait égal à :
je = (N-1)/2 - Si « T » a « N » un nombre total de nœuds et « L » est un nombre de nœuds feuilles, alors le nombre de nœuds feuilles serait égal à :
L = (N+1)/2 - Si « T » contient le nombre « L » de nœuds feuilles, alors le nombre total de nœuds serait égal à :
N = 2L - 1 - Si « T » a « L » un nombre de nœuds feuilles et « I » est un nombre de nœuds internes, alors le nombre de nœuds internes serait égal à :
je = L - 1
Qu'est-ce qu'un arbre binaire complet ?
Un arbre binaire est dit arbre binaire complet lorsque tous les niveaux sont complètement remplis sauf le dernier niveau qui est rempli par la gauche.
L'arbre ci-dessous est un arbre binaire complet :
L'arbre binaire complet est similaire à l'arbre binaire complet, à l'exception des deux différences indiquées ci-dessous :
- Le remplissage du nœud feuille doit commencer par le côté le plus à gauche.
- Il n’est pas obligatoire que le dernier nœud feuille ait le bon frère.
Comprenons les points ci-dessus à travers un exemple :
pour la boucle dans bash
Considérez l'arbre ci-dessous :
L'arbre ci-dessus est un arbre binaire complet, mais pas un arbre binaire complet car le nœud 6 n'a pas son frère droit.
Création d'un arbre binaire complet
Supposons que nous ayons un tableau de 6 éléments illustré ci-dessous :
Le tableau ci-dessus contient 6 éléments, c'est-à-dire 1, 2, 3, 4, 5, 6. Voici les étapes à suivre pour créer un arbre binaire complet :
Étape 1: Tout d’abord, nous allons sélectionner le premier élément du tableau, c’est-à-dire 1, et créer un nœud racine de l’arbre. Le nombre d'éléments disponibles dans le premier niveau est de 1.
Étape 2: Maintenant, nous allons sélectionner les deuxième et troisième éléments du tableau. Conservez le deuxième élément et le troisième élément du tableau comme enfants gauche et droit du nœud racine, respectivement indiqués ci-dessous :
Comme on peut l'observer plus haut, le nombre d'éléments disponibles dans le deuxième niveau est de 2.
algorithme de tri rapide
Étape 3: Maintenant, nous allons sélectionner les deux éléments suivants du tableau, c'est-à-dire 4 et 5. Conservez ces deux éléments à gauche et à droite du nœud 2 comme indiqué ci-dessous :
Comme nous pouvons le constater ci-dessus, les nœuds 4 et 5 sont respectivement les enfants gauche et droit du nœud 2.
Étape 4: Maintenant, nous allons sélectionner le dernier élément du tableau, c'est-à-dire 6, et le conserver comme enfant gauche du nœud 3 car nous savons que dans un arbre binaire complet, les nœuds sont remplis à partir du côté gauche comme indiqué ci-dessous :
Comme on peut le constater, le deuxième niveau contient 3 éléments.
Comprenons les différences entre l'arbre binaire complet et complet à travers les images.
- L'arbre binaire présenté ci-dessous n'est ni un arbre binaire complet ni complet. Ce n'est pas un arbre binaire complet car le nœud 3 n'a qu'un seul enfant. Ce n'est pas non plus un arbre binaire complet car les nœuds doivent être remplis du côté gauche, mais le nœud 3 a un enfant droit et n'a pas d'enfant gauche.
- L’arbre binaire présenté ci-dessous est un arbre binaire complet mais pas un arbre binaire complet. Il s'agit d'un arbre binaire complet car tous les nœuds ont soit 0, soit 2 enfants. Ce n'est pas un arbre binaire complet car le nœud 3 n'a pas d'enfants tandis que le nœud 2 a ses enfants et nous savons que les nœuds doivent être remplis du côté gauche dans un arbre binaire complet.
- L'arbre binaire présenté ci-dessous est un arbre binaire complet mais pas un arbre binaire complet. Il s'agit d'un arbre binaire complet car tous les nœuds restent remplis. Ce n'est pas un arbre binaire complet car le nœud 2 n'a qu'un seul enfant.
- L'arbre binaire présenté ci-dessous est un arbre binaire complet et complet. Il s’agit d’un arbre binaire complet car tous les nœuds restent remplis. Il s'agit d'un arbre binaire complet car tous les nœuds ont 0 ou 2 enfants.
