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

Arbre binaire complet vs Arbre binaire complet

L'arborescence binaire est une arborescence dans laquelle 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 enfants «gauches» et «droits». Les nœuds enfants contiennent une référence à leur parent. Un arbre binaire complet est un arbre binaire dans lequel tous les niveaux de l'arbre binaire sont complètement remplis à l'exception du 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 noeud de l'arbre a deux enfants sauf les feuilles de l'arbre.

Qu'est-ce qu'un arbre binaire complet??

L'arbre binaire complet est un arbre binaire dans lequel chaque nœud de l'arborescence 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 illustre 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, de sorte 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 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 l 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 tous les niveaux de l'arbre sont complètement remplis, à l'exception du dernier niveau. De plus, dans le dernier niveau, les nœuds doivent être attachés à partir de la position la plus à gauche. Un arbre binaire complet de hauteur h remplit les conditions suivantes:

- Depuis le nœud racine, le niveau supérieur au 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 du niveau supérieur au 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 nette différence. Tandis 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, telles que les segments de mémoire, doivent être des arbres binaires complets, mais pas nécessairement des arbres binaires complets. Dans un arbre binaire complet, si vous connaissez le nombre total de noeuds, le nombre de laves ou le nombre de noeuds internes, vous pouvez facilement trouver les deux autres. Mais un arbre binaire complet ne possède pas de propriété particulière reliant ces trois attributs.