Flashcards : Structures hiérarchiques et parcours d'arbres — 22 cartes

Structure hiérarchique non vide avec racine unique.

Point de départ de l’arbre, sans parent.

Élément relié à ses fils, interne ou feuille.

Nœud sans fils, terminal.

Nœud avec au moins un fils.

Au plus deux fils par nœud.

Distance d’un nœud à la racine.

Longueur du plus long chemin racine-feuille.

Partie de l’arbre à partir d’un nœud.

Elles permettent d’évaluer la taille et la profondeur.

Standardiser la structure pour traitement algorithmique.

Représenter données hiérarchiques, structures, expressions.

Explorer le plus profondément avant de revenir en arrière.

Explorer niveau par niveau, par file.

Θ(n log n) dans le pire cas.

Feuilles : pas d’enfant, internes : au moins un enfant.

Plus de nœuds peut augmenter la hauteur.

Réorganiser fils pour limiter à deux par nœud.

Racine, nœuds, feuilles, parcours.

Préfixe, infixe, postfixe.

Utilise une file, explore niveau par niveau.

h+1 ≤ n ≤ (a^{h+1}-1)/(a-1).