Arbre binaire complet vs arbre binaire complet
L'arbre binaire est un arbre où chaque nœud a un ou deux enfants. Dans un arbre binaire, un nœud ne peut pas avoir plus de deux enfants. Dans un arbre binaire, les enfants sont nommés comme des enfants «à gauche» et «à droite». Les nœuds enfants contiennent une référence à leur parent. Un arbre binaire complet est un arbre binaire dans lequel chaque niveau de l'arbre binaire est complètement rempli sauf le dernier niveau. Dans le niveau non rempli, les nœuds sont attachés à partir de la position la plus à gauche. Un arbre binaire complet est un arbre dans lequel chaque nœud de l'arbre a deux enfants à l'exception des feuilles de l'arbre.
Qu'est-ce que l'arbre binaire complet?
L'arbre binaire complet est un arbre binaire dans lequel chaque nœud de l'arbre a exactement zéro ou deux enfants. En d'autres termes, chaque nœud de l'arbre, à l'exception des feuilles, a exactement deux enfants. La figure 1 ci-dessous représente un arbre binaire complet. Dans un arbre binaire complet, le nombre de nœuds (n), le nombre de laves (l) et le nombre de nœuds internes (i) sont liés d'une manière spéciale de sorte que si vous connaissez l'un d'entre eux, vous pouvez déterminer les deux autres valeurs comme suit:
1. Si un arbre binaire complet a i nœuds internes:
- Nombre de feuilles l = i + 1
- Nombre total de nœuds n = 2 * i + 1
2. Si un arbre binaire complet a n nœuds:
- Nombre de nœuds internes i = (n-1) / 2
- Nombre de feuilles l = (n + 1) / 2
3. Si un arbre binaire complet a 1 feuilles:
- Nombre total de nœuds n = 2 * l-1
- Nombre de nœuds internes i = l-1
Qu'est-ce que l'arbre binaire complet?
Comme le montre la figure 2, un arbre binaire complet est un arbre binaire dans lequel chaque niveau de l'arbre est complètement rempli sauf le dernier niveau. De plus, au dernier niveau, les nœuds doivent être attachés à partir de la position la plus à gauche. Un arbre binaire complet de hauteur h satisfait aux conditions suivantes:
- A partir du nœud racine, le niveau au-dessus du dernier niveau représente un arbre binaire complet de hauteur h-1
- Un ou plusieurs nœuds du dernier niveau peuvent avoir 0 ou 1 enfant
- Si a, b sont deux nœuds dans le niveau au-dessus du dernier niveau, alors a a plus d'enfants que b si et seulement si a est situé à gauche de b
Quelle est la différence entre un arbre binaire complet et un arbre binaire complet?
Les arbres binaires complets et les arbres binaires complets ont une nette différence. Alors qu'un arbre binaire complet est un arbre binaire dans lequel chaque nœud a zéro ou deux enfants, un arbre binaire complet est un arbre binaire dans lequel chaque niveau de l'arbre binaire est complètement rempli sauf le dernier niveau. Certaines structures de données spéciales comme les tas doivent être des arbres binaires complets alors qu'ils n'ont pas besoin d'être des arbres binaires complets. Dans un arbre binaire complet, si vous connaissez le nombre de nœuds au total ou le nombre de laves ou le nombre de nœuds internes, vous pouvez trouver les deux autres très facilement. Mais un arbre binaire complet n'a pas de propriété spéciale reliant ces trois attributs.
