Pointeurs et références (Arbres binaires)

Un arbre est un ensemble de noeuds, pas une classe. La classe est la classe Noeud, dont les instances sont des … noeuds.

De plus, une référence est une deuxième "étiquette" sur une variable. Bien que le code assembleur généré pour un pointeur et une référence soit le même, ces deux notions sont conceptuellement différentes. Dans la pratique, une référence est un pointeur constant (on ne peut pas changer l'adresse pointée), non nul et avec déréférencement automatique, tout cela offrant des garanties fortes. Mais je n'aime pas le voir comme ça, je préfère plutôt garder en tête leur différence conceptuelle. En revanche, les garanties offertes par les références permettent de choisir facilement entre pointeurs et références (globalement, références autant que faire se peut, pointeurs sinon).

Lu'!

Cela dépend de la sémantique que ton langage accorde au mot référence en fait … Une référence n'a pas le même sens en C++ et en Java typiquement. Le truc c'est que si tu te places en C++, yu ne peux pas produire une structure de données type arbre avec des références à moins de détourner la manière dont tu les utilises. Ce sera nécessairement des pointeurs (intelligents).

Pour un arbre où un noeud peut avoir deux noeuds fils, oui, tu aura donc deux références.

Pour les algorithmes, ils sont assez simples, as-tu essayer de les appliquer à un arbre simple ?
Ils ont juste pour objectif de parcourir tous les noeuds, mais tu verras qu'en changeant simplement le moment où on affiche la valeur on arrive à obtenir tous les ordres définis (préfixe, postfixe, infixe). Tu as un exemple illustrer sur ce pdf à la page 8.

• Je ne comprends pas la structure de ces trois pseudo-code (c'est un peu plus bas dans la partie 2 "Algorithmes récursifs"). C'est un algorithme récursif, puisque qu'on fait un appel récursif direct sur la fonction Parcours mais en gros, il renvoi quoi le programme en sortie?

Les trois algorithmes ne retournent rien, ils affichent les nœuds dans un certain ordre. On utilise ces algorithmes en remplaçant l'affichage des nœuds par un certain traitement (quelconque) à effectuer sur les nœuds. Parfois, il faut avoir traité le sous-arbre gauche avant de pouvoir traiter le nœud, avant de pouvoir traiter le sous-arbre droit, dans ce cas on utilise un parcours infixe. Parfois il faut avoir traité les deux sous-arbres avant de pouvoir traiter le nœud, on utilise alors un parcours postfixe, etc.

Mais ça n'est pas très important si tu t'intéresses à la récursivité d'un point de vue non algorithmique (je crois que c'est le cas). Il n'y a pas de notion d'ordre dans le traitement des différentes composantes de l'arbre (le nœud, le sous-arbre gauche et le sous-arbre droit).

Par exemple, si les nœuds sont étiquetés par des nombres et que tu veux sommer tous les nombres dans un arbre, on peut faire comme suit. Un arbre est soit « vide », noté ∅, soit composé d'un nombre x (l'étiquette du nœud), un sous-arbre gauche L et un sous-arbre droit R, noté (x,L,R). Alors tu définis ta fonction récursivement en disant f(∅) = 0 et f(x,L,R) = x+f(L)+f(R).

Le vocabulaire de C++ est un peu confusant dans ce contexte.

Dans le cas général (dans n'importe quel langage), il faut voir une référence comme une étiquette. Quel que soit la techno ou l'implémentation derrière, une référence, au sens large, c'est "un lien qui me permet de récupérer une valeur qui se situe ailleurs".

Dans ce cas, ça signifie que les fils d'un noeud n'appartiennent pas au (ne font pas partie du) père : la référence peut être cassée sans que le fils ne soit détruit, et celui-ci peut tout à fait être référencé par un autre père.

Dans cette tournure d'esprit, les pointeurs du C sont un style particulier (une implémentation du concept) de référence. Et les références du C++ en sont une autre.

@blo ygh : ta définition est incomplète. Que vaut f(42) ?

Edit: tu as raison. Au temps pour moi.

Même (je dirais surtout) pour étudier les structures de données récursives, il est assez frustrant de devoir en même temps se battre avec des considérations d'implémentations qui n'ont pas grand chose à voir avec le problème. Si tu prends par exemple Haskell qui permet facilement de définir des structures de données récursives (c'est même comme ça que sont définies les listes dans ce langage), définir l'arbre binaire tel qu'imaginé par blo yhg est simple comme bonjour :

1

data Tree a = Empty | Node a (Tree a) (Tree a)

On dit littéralement qu'un arbre rempli d'éléments avec le type générique a est soit vide, soit composé d'un nœud avec un élément de type a auquel sont raccordés deux arbres.

On peut aussi définir des arbres sans autoriser les arbres vides (selon ce que l'on souhaite faire) :

1

data Tree a = Leaf a | Node a (Tree a) (Tree a)

où cette fois on dit que les arbres sont soient une feuille avec un élément, soit un noeud avec deux arbres qui partent.

Je ne suis bien sûr pas en train de te dire d'apprendre le Haskell pour pouvoir apprendre les types de données récursives, mais que les notions de références et d'objets n'ont réellement rien à faire avec la notion de structure de données récursives, même (surtout) d'un point de vue algorithmique.

Du coup, si il n'y a qu'un conseil à te donner, c'est déjà que tu sois sûr de comprendre les notions de références et d'objets avant d'essayer de les utiliser pour implémenter une structure récursive. Sinon tu te bats sur deux fronts relativement difficiles en même temps.