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

Considérons un arbre binaire dont les nœuds sont dessinés en forme d'arbre. Commencez maintenant à numéroter les nœuds de haut en bas et de gauche à droite. Un arbre complet possède ces propriétés :

Si n a des enfants, alors tous les nœuds dont le numéro est inférieur à n ont deux enfants.

Si n a un enfant, ce doit être l'enfant de gauche et tous les nœuds inférieurs à n ont deux enfants. De plus, aucun nœud dont le numéro est supérieur à n n'a d'enfant.

Si n n'a pas d'enfants, alors aucun nœud dont le numéro est supérieur à n n'a d'enfants.

Un arbre binaire complet peut être utilisé pour représenter un tas. Il peut être facilement représenté dans une mémoire contiguë sans espace (c'est-à-dire que tous les éléments du tableau sont utilisés, à l'exception de l'espace qui peut exister à la fin).

Answer 2

L'arbre binaire complet est un arbre binaire complet mais l'inverse n'est pas possible, et si la profondeur du binaire est n, le nombre de noeuds dans l'arbre binaire complet est ( 2^n-1 ). Il n'est pas nécessaire que l'arbre binaire ait deux enfants, mais dans l'arbre binaire complet, chaque nœud n'a ni deux ni aucun enfant.

Answer 3

Pour commencer par les bases, il est très important de comprendre l'arbre binaire lui-même pour en comprendre les différents types.

Un arbre est un arbre binaire si et seulement si :-

- Il possède un nœud racine, qui peut ne pas avoir de nœuds enfants (0 nœud enfant, arbre NUL).

-Le noeud racine peut avoir 1 ou 2 noeuds enfants. Chacun de ces nœuds forme lui-même un arbre abinaire

-Le nombre de noeuds enfants peut être 0 ,1 ,2....... pas plus de 2

-Il existe un chemin unique entre la racine et tous les autres nœuds.

Exemple :

        X
      /    \
     X      X
          /   \
         X     X

Pour en venir aux terminologies que vous avez demandées :

Un arbre binaire est un arbre binaire complet (de hauteur h, nous prenons le nœud racine comme 0) si et seulement si :-

les niveaux 0 à h-1 représentent un arbre binaire complet de hauteur h-1

- Un ou plusieurs nœuds du niveau h-1 peuvent avoir 0 ou 1 nœud enfant.

Si j,k sont des noeuds du niveau h-1, alors j a plus de noeuds enfants que k si et seulement si j est à gauche de k , c'est-à-dire que le dernier niveau (h) peut ne pas contenir de noeuds feuilles, mais ceux qui sont présents doivent être déplacés vers la gauche.

Exemple :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 

Un arbre binaire est un arbre strictement binaire si et seulement si :-

Chaque nœud a exactement deux nœuds enfants ou aucun nœud.

Exemple :

         X
       /   \
      X     X 
          /   \
         X      X
        / \    / \ 
       X   X  X   X 

Un arbre binaire est un arbre binaire complet si et seulement si :-

Chaque nœud non feuillu a exactement deux nœuds enfants.

Tous les nœuds feuilles sont au même niveau

Exemple :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Vous devriez également savoir ce qu'est un arbre binaire parfait ?

Un arbre binaire est un arbre binaire parfait si et seulement si :-

- est un arbre binaire complet

- Tous les nœuds feuilles sont au même niveau

Exemple :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Je suis désolé, je ne peux pas poster d'images car je n'ai pas 10 de réputation. J'espère que cela vous aidera et aidera les autres !

Answer 4

Dans mon expérience limitée avec l'arbre binaire, je pense :

1. Arbre strictement binaire :Tous les nœuds, à l'exception des nœuds feuilles, ont deux enfants ou n'ont qu'un nœud racine.
2. Arbre binaire complet : Un arbre binaire de H contenant strictement(ou exactement) 2^(H+1) -1 noeuds il est clair que chaque niveau a le plus de noeuds. Ou en bref, un arbre binaire strict où tous les nœuds des feuilles sont au même niveau.
3. Arbre binaire complet : C'est un arbre binaire dans lequel chaque niveau, sauf éventuellement le dernier, est complètement rempli, et tous les nœuds sont aussi à gauche que possible.

Answer 5

Considérons un arbre binaire de hauteur "h". Un arbre binaire est appelé arbre binaire complet si toutes les feuilles sont présentes à la hauteur 'h' ou 'h-1' sans aucun nombre manquant dans la séquence.

                   1
                 /   \
              2       3
            /    \         
         4        5

C'est un arbre binaire complet.

                   1
                 /   \
              2       3
            /        /    
         4         6    

Ce n'est pas un arbre binaire complet car il manque le nœud du numéro 5 dans la séquence.