8.2. Arbres multiples

Bien que cela soit rarement utilisé, il est tout à fait possible de construire un arbre de degré n à l'aide d'une structure telle que :

        const n = . . . ;

    type Element = record
                     Info: ...;
                     Descendants:array[1..n]
                                 of ^Element;
                      end; { Element }

8.2.1. Représentation d'arbre multiple sous forme d'arbre binaire

Il arrive souvent que l'on ait besoin de construire des arbres multiples dont on ne connaît pas à l'avance le degré. A moins de réserver pour chaque noeud un suffisamment grand nombre de pointeurs vers des descendants pour être sûr qu'il y en ait toujours assez, on est amené à représenter les arbres multiples à l'aide d'arbres binaires.

On utilise alors un pointeur fils, pointant vers le premier des descendants, et un pointeur frère, pointant vers le prochain noeud ayant le même ancêtre. La différence principale avec un arbre multiple réel est que l'on n'a pas accès directement à tous les descendants d'un noeud; on est obligé de passer par le premier descendant pour atteindre le deuxième, et ainsi de suite. Il faut aussi bien se rendre compte que les deux pointeurs de chaque noeud n'ont pas la même signification que pour un arbre binaire habituel.

Fig. 8.7. Passage d'un arbre multiple à un arbre binaire.

8.3. Représentation d'arbres à l'aide de tableaux

Table des matières.

Site Hosting: Bronco