TOUT CE QU’IL FAUT SAVOIR SUR LES ARBRES DE JAVA

Un arbre de java est constitué d’un ensemble de nœuds ou de sommets et d’un ensemble d’arêtes ou d’arcs qui répondent à certaines exigences :

• Il existe une hiérarchie de nœuds, de sorte que chaque nœud enfant reçoit un bord d’un nœud parent. De cette façon, la relation parent-enfant est établie.
• Le nœud où commence la hiérarchie est appelé nœud racine. Ce nœud ne reçoit pas d’arcs d’un autre nœud, en d’autres termes, il n’est pas un enfant d’un nœud parent.
•  Il existe un chemin unique entre la racine et n’importe lequel des nœuds de l’arbre

Nous allons maintenant nous pencher sur la terminologie relative aux arbres de java. Nous allons d’abord examiner les types de nœuds que nous pourrions trouver dans un arbre de java. Nous avons vu qu’il existe un nœud spécial, le nœud racine, qui n’a pas de parents. Le cas des nœuds qui n’ont pas d’enfants est celui des nœuds externes ou des nœuds de feuilles. Les autres nœuds sont internes, lorsqu’ils ont une progéniture. Nous dirons qu’un nœud est un descendant d’un autre nœud, s’il est un enfant de celui-ci ou un descendant de ses enfants. Les descendants déterminent un sous-arbre avec la racine du nœud descendant.

Nous allons maintenant voir les concepts qui nous donnent une idée de la topologie de l’arbre. Ce sont les concepts de chemin, de longueur et de profondeur :

• Le chemin entre deux nœuds est la séquence d’arcs qui mène du premier au second. La longueur est le nombre d’arêtes qu’il contient.
• La profondeur d’un nœud est la longueur du chemin de la racine à ce nœud.
• La hauteur d’un arbre est la profondeur maximale entre tous les nœuds d’extrémité de l’arbre. En d’autres termes, “la profondeur du nœud le plus profond”.

Pour simplifier l’étude des arbres de java, nous allons nous pencher sur le cas des arbres de java binaires. Un arbre de java binaire est un arbre dans lequel chaque nœud a 0 ou 2 enfants (l’enfant de gauche et l’enfant de droite). Cet arbre peut être ordonné si, pour chaque nœud, il existe un ordre linéaire pour tous ses enfants, c’est-à-dire que si nous avons l’ordre “moins que”, un arbre sera ordonné si, pour chaque nœud, ses enfants sont moins que le père.

Voyons comment la taille de l’arbre de java serait calculée à partir de cette définition 

Nous définissons une fonction auxiliaire qui calcule la taille d’un sous-arbre sous un nœud. Cette méthode calcule une longueur 0 si le nœud est nul. Sinon, la longueur sera la somme des tailles des nœuds enfants plus un, correspondant au nœud actuel.