Différence entre "arbre binaire complet", "arbre binaire strict", "arbre binaire complet" ?

Question

Je suis confus quant à la terminologie des arbres ci-dessous, j'ai étudié l'arbre, et je suis incapable de faire la distinction entre ces arbres :

a) Arbre binaire complet

b) Arbre binaire strict

c) Arbre binaire complet

Veuillez m'aider à faire la différence entre ces arbres. Quand et où ces arbres sont utilisés dans la structure des données ?

Answer 1

Un arbre parfait :

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ / \ / \ / \
x x x x x x x x

Arbre complet :

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ /
x x x

Arbre strict/complet :

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x

Answer 2

Wikipedia a donné

Un arbre binaire complet (parfois appelé arbre binaire propre, arbre à deux branches ou arbre strictement binaire) est un arbre dans lequel chaque nœud autre que les feuilles a deux enfants.

Vous n'avez donc aucun nœud avec un seul enfant. Il semble que ce soit la même chose que l'arbre binaire strict.

Voici une image d'un arbre binaire complet/strict, tirée de Google :

Un arbre binaire complet est un arbre binaire dans lequel chaque niveau, sauf éventuellement le dernier, est complètement rempli, et tous les nœuds sont aussi loin que possible à gauche.

Cela semble signifier un arbre équilibré.

Voici une image d'un arbre binaire complet, provenant de google, la partie arbre complet de l'image est en bonus.

Answer 3

Il y a une différence entre un ARBRE STRICTE et un ARBRE PLEIN BINAIRE.

1) ARBRE BINAIRE COMPLET : Un arbre binaire de hauteur h qui contient exactement (2^h)-1 éléments est appelé un arbre complet. arbre binaire . (Ref : Pg 427, Structures de données, algorithmes et applications en C++. (University Press), deuxième édition par Sartaj Sahni).

ou en d'autres termes

Dans un ARBRE BINAIRE COMPLET, chaque nœud a exactement 0 ou 2 enfants et tous les nœuds feuilles sont au même niveau.

Par exemple : Ce qui suit est un ARBRE BINAIRE COMPLET :

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 

2) ARBRE BINAIRE STRICT : Chaque nœud a exactement 0 ou 2 enfants.

Par exemple : Ce qui suit est un ARBRE BINAIRE STRICTE :

         18
       /     \   
     15       30    
    /  \          
  40    50

Je pense qu'il n'y a pas de confusion dans la définition d'un arbre binaire complet, mais pour que le post soit complet, je voudrais dire ce qu'est un arbre binaire complet.

3) ARBRE BINAIRE COMPLET : Un arbre binaire est un arbre binaire complet si tous les niveaux sont complètement remplis, sauf éventuellement le dernier niveau, et que ce dernier a toutes les clés les plus à gauche possible.

Par exemple : Ce qui suit est un ARBRE BINAIRE COMPLET :

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 

Nota: Ce qui suit est également un arbre binaire complet :

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40

Answer 4

Avis de non-responsabilité - La principale source de certaines définitions est wikipedia, toute suggestion pour améliorer ma réponse est la bienvenue.

Bien que ce post ait une réponse acceptée et qu'il s'agisse d'une bonne réponse, j'étais encore dans la confusion et j'aimerais ajouter quelques précisions concernant la différence entre ces termes.

(1) ARBRE BINAIRE COMPLET- Un arbre binaire complet est un arbre binaire dans lequel chaque nœud autre que les feuilles a deux enfants. arbre strictement binaire .

Les deux exemples ci-dessus sont des exemples d'arbres complets ou strictement binaires.

(2) ARBRE BINAIRE COMPLET- La définition de l'arbre binaire complet est assez ambiguë : un arbre binaire complet est un arbre binaire dans lequel chaque niveau.., sauf peut-être le dernier est complètement rempli, et tous les nœuds sont aussi loin que possible à gauche. Il peut avoir entre 1 et 2h nœuds, le plus à gauche possible, au dernier niveau h

Remarquez les lignes en italique.

L'ambiguïté réside dans les lignes en italique, "sauf éventuellement le dernier", ce qui signifie que le dernier niveau peut aussi être complètement rempli, c'est-à-dire que cette exception ne doit pas toujours être satisfaite. Si l'exception n'est pas satisfaite, alors c'est exactement comme la deuxième image que j'ai postée, qui peut aussi être appelée arbre binaire parfait . Ainsi, un arbre binaire parfait est également plein et complet, mais pas l'inverse, ce qui sera clarifié par une autre définition que je dois énoncer :

ARBRE BINAIRE PRESQUE COMPLET- Lorsque l'exception dans la définition de l'arbre binaire complet est valable, on parle d'arbre binaire presque complet ou d'arbre binaire presque complet. Il s'agit simplement d'un type d'arbre binaire complet, mais une définition distincte est nécessaire pour la rendre plus claire.

Ainsi, un arbre binaire presque complet ressemblera à ceci, vous pouvez voir sur l'image que les nœuds sont aussi loin à gauche que possible, il s'agit donc plutôt d'un sous-ensemble de l'arbre binaire complet, pour dire plus rigoureusement que tout arbre binaire presque complet est un arbre binaire complet, mais pas l'inverse.. :

Answer 5

En conclusion des réponses ci-dessus, voici la différence exacte entre les arbres binaires complets/strictement, complets et parfaits.

1. Arbre complet/trictement binaire :- Chaque nœud, à l'exception des nœuds feuilles, a deux enfants.

2. Arbre binaire complet Chaque niveau, sauf le dernier, est entièrement rempli et tous les nœuds sont justifiés à gauche.

3. Arbre binaire parfait Chaque nœud, à l'exception des nœuds feuilles, a deux enfants et chaque niveau (y compris le dernier) est entièrement rempli.