Une autre structure de données non-linéaire commune est l'arbre.
Dans ce diagramme ci-dessus, nous pouvons voir que le point de départ, ou le noeud de racine, est entouré dans la couleur bleue. Un noeud est une structure simple qui tient des données et des liens sur d'autres noeuds. Dans ce cas-ci, notre noeud de racine contient la corde « John » de données et trois liens aux autres noeuds. Noter que le groupe de noeuds cerclés dans le rouge n'ont aucun lien (childs). Ces noeuds sont à l'extrémité des branches et ils s'appellent convenablement en tant que des feuilles ou noeuds de feuille. Dans notre diagramme, les noeuds sont reliés ensemble avec les lignes noires pleines appelées des arcs ou les bords. Ces bords montrent les rapports entre les noeuds dans l'arbre.
Un rapport important dans l'arbre binaire est le rapport de parent-enfant. Les noeuds de parent ont au moins un bord au noeud s'abaissent dans l'arbre. Ce noeud inférieur s'appelle le noeud d'enfant. Les noeuds peuvent avoir plus d'un enfant, mais les enfants peuvent seulement avoir un parent simple. Noter que le noeud de racine n'a aucun parent, et les noeuds de feuille n'a aucun enfant. Le dispositif final à la note dans notre diagramme est le sous-arbre. À chaque niveau de l'arbre, nous pouvons voir que la structure arborescente est répétée. Par exemple, les deux noeuds représentant « Charles » et « Rick » composent un arbre très simple avec « Charles » en tant que le noeud de racine et et « Rick » comme noeud simple de feuille.
Des arbres sont mis en application dans la mémoire d'ordinateur. Nous commencerons en présentant la structure arborescente simple appelée l'arbre binaire. Les arbres binaires ont la restriction que les noeuds ne peuvent pas avoir plus de deux enfants. Avec cette restriction, nous pouvons facilement déterminer comment représenter un noeud binaire simple dans la mémoire. Notre noeud devra réserver la mémoire pour les données et deux indicateurs (pour diriger deux childs de ce noeud).
|
