Différence entre l'arbre binaire complet et l'arbre binaire complet

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 à leurs parents. Un arbre binaire complet est un arbre binaire dans lequel chaque niveau de l'arbre binaire est complètement rempli, sauf le dernier niveau. Au 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 de manière spéciale telle que si vous connaissez l'un d'eux, vous pouvez déterminer les deux autres Valeurs comme suit:

1. Si un arbre binaire complet a des 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 des 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:

- À 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 au dernier niveau peuvent avoir 0 ou 1 enfants

- Si A, B est 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 l'arbre binaire complet et l'arbre binaire complet?

Les arbres binaires complets et les arbres binaires complets ont une différence claire. Alors qu'un arbre binaire complet est un arbre binaire dans lequel chaque nœud n'a aucun 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 totaux 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 concernant ces trois attributs.