Opérations pouvant être effectuées sur une liste :

• créer une liste vide
• tester si une liste est vide

Les arbres sont des types abstraits permettant de structurer les données.

Un arbre binaire un cas particulier d'arbre qui peut se présenter sous la forme :

Vocabulaire :

• nœud : chaque élément de l'arbre (ex : A, B, …)
• nœud racine : premier nœud de l'arbre (ici : A)
• nœud fils : les nœuds D et E sont les fils du nœud B
• nœud père : le nœud B est le père des nœuds D et E
• feuille : nœud n'ayant aucun fils (ex : D)
• arête : segment qui relie deux nœuds
• profondeur d'un nœud : nombre de nœuds du chemin entre la racine et le nœud (ex : F est à une profondeur de 3)
• hauteur d'un noeud : profondeur maximale de l'arbre (ici : 5)

Dans un arbre binaire, chaque noeud possède au plus 2 fils (souvent appelés fils droit et fils gauche).

Le sous-arbre d'un noeud est le deux sous-arbre ayant pour racine le fils du noeud. Chaque noeud peut avoir jusqu'à deux sous-arbres (un par fils).