Structure, recherche et tri

Representation

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13
          

Triplet (gauche, valeur, droite). Les pointeurs lient les noeuds.

Parcours classiques

Prefixe (racine, gauche, droite), infixe (gauche, racine, droite), postfixe (gauche, droite, racine).

Arbre binaire de recherche

Invariant: valeurs du sous-arbre gauche < racine < sous-arbre droit.

Tri par arbre

Inserer tous les elements dans un BST puis parcourir en infixe.