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).
|
