Bac : NSI arbres binaires parcours

Qu'est-ce qu'un arbre binaire?

Un arbre binaire est une structure de données où chaque nœud a au plus deux enfants. Les enfants sont généralement appelés "gauche" et "droite".

Vrai ou faux: Un arbre binaire peut avoir plus de deux enfants.

Faux. Un arbre binaire a par définition au maximum deux enfants par nœud.

Qu'est-ce qu'un nœud feuille?

Un nœud feuille est un nœud d'un arbre binaire qui n'a pas d'enfants. Il est au bout d'un chemin.

Quels sont les types d'arbres binaires?

- Arbre binaire complet - Arbre binaire parfait - Arbre binaire équilibré

Complétez: Un arbre binaire est équilibré si la hauteur des sous-arbres diffère de ____.

1. Cela signifie que les branches de l'arbre ont des hauteurs à peu près égales.

Quelle est la hauteur d'un arbre binaire parfait avec 7 nœuds?

La hauteur est de 2. Un arbre parfait a tous ses nœuds remplis et suit la formule $\displaystyle h = ext{log}_2(n + 1)$.

Qu'est-ce qu'un parcours en profondeur?

Un parcours en profondeur (DFS) explore un nœud puis ses enfants avant de passer au nœud suivant. Les méthodes incluent préordre, en ordre, et postordre.

Vrai ou faux: Tous les arbres binaires sont des arbres de recherche.

Faux. Un arbre binaire de recherche a une structure spécifique où les nœuds fils gauche sont inférieurs et les nœuds fils droit sont supérieurs à leur parent.

Quelle est la différence entre un arbre binaire et un arbre binaire de recherche?

Un arbre binaire n'a pas de contrainte sur l'ordre des nœuds, tandis qu'un arbre binaire de recherche doit respecter l'ordre croissant ou décroissant.

Qu'est-ce qu'un nœud racine?

C'est le nœud supérieur d'un arbre binaire, à partir duquel tous les autres nœuds sont accessibles.

Qu'est-ce qu'une feuille en termes d'arbre binaire?

Une feuille est un nœud sans enfants, représentant la fin d'un chemin dans l'arbre.

Énumérez les propriétés d'un arbre binaire équilibré.

- Hauteur minimale - Différence de hauteur maximale de 1 entre sous-arbres - Plus de nœuds peuvent être ajoutés sans déséquilibrer

Qu'est-ce que le parcours en ordre ?

C'est un parcours qui visite d'abord le sous-arbre gauche, ensuite le nœud courant, puis le sous-arbre droit.

Parcours préordre : ordre des visites ?

Visite d'abord le nœud courant, puis le sous-arbre gauche et enfin le sous-arbre droit.

Vrai ou faux : le parcours postordre visite le nœud avant ses enfants.

Faux. Le parcours postordre visite d'abord les enfants puis le nœud courant.

Complétez : En parcours préordre, on traite le nœud avant ____ .

ses sous-arbres.

Exemple de parcours en ordre sur : 4, 2, 5, 1, 3.

Résultat : 1, 2, 3, 4, 5.

Qu'est-ce que le parcours postordre ?

On visite d'abord le sous-arbre gauche, ensuite le sous-arbre droit, puis le nœud courant.

Comparaison : préordre vs postordre.

Préordre : nœud, gauche, droit. Postordre : gauche, droit, nœud.

Quel est le résultat du parcours préordre sur : 1, 2, 3 ?

1, 2, 3 (visite racine d'abord).

Quelles traversées sont utilisées pour les arbres binaires ?

Préordre, en ordre, postordre.

Effet du parcours en ordre sur un arbre binaire trié ?

Il renvoie les valeurs dans l'ordre croissant.

Énumérez les trois types de parcours.

Préordre, en ordre, postordre.

Exemple de parcours postordre sur : 4, 2, 5, 1, 3.

Résultat : 3, 1, 2, 5, 4.