Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arbre binaire - Coggle Diagram
Arbre binaire
Mesures dans l'arbre
-
-
-
hauteur arbre=hauteur de racine=
- long chemin entre racine et une feuille
-
déf
-
special
-
-
complet: rempli, chaque noeud a 2 fils
nb de noeuds d'un arbre complet de hauteur h: 2^(h+1)-1
parfait tout rempli sauf dernier niveau où c'est rempli qu'à gauche
<> dégénéré= uniquement noeuds avec fils unique
partiellement ordonné ens étiquettes ordonnées (clés), tout clé noeud père < noeuds fils et vice versa
-
représentation arbre binaire
type Arbre=^noeud
^noeud=enregistrement
valeur: t
fg, fd: Arbre
-
arbre binaire de recherche
pour tout noeud x, tout y (sag), tout z (sad)
clé y<clé x < clé z
-
-
parcours
préfixe: 1er rencontre ds parcours depuis racine
suffixe: dernier rencontre ds parcours depuis racine
infixe: sag-x-sad, partant de la dernière feuille en bas à gauche
-