Est-ce un arbre binaire complet?

Voici l'arbre binaire en question. Les feuilles sont a, b, c, d et les bords sont étiquetés 0 ou 1.Est-ce un arbre binaire complet?

. 
/\ 
    a . 
    /\ 
    b . 
    /\ 
     c d

Il me semble qu'il est un arbre binaire complet, comme chaque nœud est soit une feuille ou a deux nœuds enfants , cependant j'ai ce sentiment qu'on nous a dit que ce n'est pas un arbre binaire complet. Si non, pourquoi n'est-ce pas?

Si un nœud a un enfant qui est une feuille, cela ne compte-t-il pas comme un nœud enfant?

Source

2009-05-25 Adam Taylor

[Cette page] (http://www.differencebetween.com/difference-between-complete-binary-tree-and-vs-full-binary-tree) résoudra tous vos doutes. –

Vous confondez un arbre binaire parfait avec un arbre binaire complet. Un arbre binaire parfait est un arbre binaire complet avec tous les nœuds feuilles au même niveau. Alors oui, l'image est un arbre binaire complet. Une feuille est définie comme un noeud sans noeud enfant.
Ainsi, un arbre binaire complet est un arbre binaire dans lequel chaque noeud a zéro ou deux enfants.

Wikipedia aide très bien avec les définitions. Assurez-vous de vérifier.

Source

2009-05-25 15:51:52

J'allais dire que ce n'est pas équilibré. Mais merci pour une nouvelle définition. Vous apprenez quelque chose tous les jours. – uriDium

Balanced est une autre histoire. Cela signifie que la différence de profondeur entre l'enfant droit et l'enfant gauche de chaque nœud est au plus égale à un. –

Cela ne devrait pas être "Alors oui, l'image est un arbre binaire ** parfait **"? – sharkin

Oui, un arbre avec chaque noeud a zéro ou deux enfants, c'est un arbre binaire.

Source

2010-10-16 13:48:26

Est-ce un arbre binaire complet?

Répondre

Questions connexes