Pointeurs et références (Arbres binaires)

Le problème exposé dans ce sujet a été résolu.

Bonjour, je travail un peu sur les structures de données récursives pour comprendre les arbres binaires et comment écrire un ou deux algorithmes simples (en pseudo-code) et ce qui m'aidera aussi un arithmétique (récursivité). J'ai commencé à lire une page wikiversité et il y a quelques petites choses que je ne comprend pas, parce que ça fait un bail que j'ai pas vraiment fait de programmation pur et orienté objet (c++, VB.net, Java…) :

  • Un arbre, c'est une structure de donnée, comme une classe et les nœuds sont des instances de cette classe (des objets?)?

  • J'ai du mal à comprendre cette phrase dans la première partie : "(…) la case blanche représente une référence vers ce même type et la flèche indique que cette référence est utilisée et pointe vers l'instance concernée."

Une référence, c'est une valeur qui indique une adresse mémoire? C'est quoi exactement (en comparaison avec les pointeurs)? Du coup, quel est l’intérêt pour les "connexions" entre chaque nœuds de l'arbre?

  • 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?

Merci pour vos réponses. :-)

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

+0 -0

Dans le cas d'un nœud du coup, il y a deux références qui pointent vers d'autres nœud? C'est ça que j'ai du mal à conceptualiser : je ne comprends pas le mécanisme. Bon après, comme je fais pas de programmation pure et dure, ce n'est peut-être pas le plus important.

En revanche, si vous avez une petite explication pour les pseudo-codes…

+0 -0

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.

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

+0 -0

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.

+1 -0

J'ai commencé à lire une page wikiversité et il y a quelques petites choses que je ne comprend pas, parce que ça fait un bail que j'ai pas vraiment fait de programmation pur et orienté objet (c++, VB.net, Java…) :

  • Un arbre, c'est une structure de donnée, comme une classe et les nœuds sont des instances de cette classe (des objets?)?

  • J'ai du mal à comprendre cette phrase dans la première partie : "(…) la case blanche représente une référence vers ce même type et la flèche indique que cette référence est utilisée et pointe vers l'instance concernée."

Une référence, c'est une valeur qui indique une adresse mémoire? C'est quoi exactement (en comparaison avec les pointeurs)? Du coup, quel est l’intérêt pour les "connexions" entre chaque nœuds de l'arbre?

Ozmox

Ça semble vachement contre-productif de commencer à étudier les types de données récursifs en se concentrant d'abord sur des notions qui n'ont rien à voir comme les références ou les classes, mais JDÇJDR.

une référence, au sens large, c'est "un lien qui me permet de récupérer une valeur qui se situe ailleurs".

nohar

Pour éviter la confusion, je préfère le terme "indirection" pour la cas général et "reference" pour les références au sens du C++

+1 -0

C'est pas tout à fait en rapport avec la question, mais je fais de la pub pour mon tuto sur les arbres binaires qui est toujours, et qui peut être une source d'informations complémentaire.

Aussi, j'aimerais bien voir ton implémentation en C++, ça peut être intéressant d'y jeter un œil :)

Oui, en fait j'ai légèrement frôler la prog orienté objet car je souhaitais me remettre au c++ et j'ai été pris de curiosité, mais pour la récursivité d'un point de vue non algorithmique, oui, c'est inutile. D'ailleurs, blo yhg répond bien à cela, merci pour vos explications!

Oui, en fait j'ai légèrement frôler la prog orienté objet car je souhaitais me remettre au c++ et j'ai été pris de curiosité, mais pour la récursivité d'un point de vue non algorithmique, oui, c'est inutile. D'ailleurs, blo yhg répond bien à cela, merci pour vos explications!

Ozmox

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.

Petite question : Est-ce qu'on utilise les arbres binaires en mathématiques?

Oui

Est-ce qu'on peut les considérés comme des ensembles ordonnées (ou pas)?

Si on veut, pour quelle relation d'ordre ?

Edit : ah tu veux dire un arbre ~ un ensemble ordonné, euh si tu veux.

Pourquoi ces questions ?

+0 -0

Par exemple, la fonction de blo yhg, comment est-ce qu'on la définirait en écriture mathématique?

Par exemple, on peut considérer la fonction racine carrée comme une fonction de $\mathbb R^+$ dans $\mathbb R$. Quand serait-il pour la fonction de blo yhg? Déjà, elle prend trois éléments. L et R sont des sous-arbres, donc des ensembles de nœuds… En gros, c'est ça que j'ai du mal à visualiser.

+0 -0

Ah je comprends ce que tu veux dire. Je n'ai pas de document intéressant à te conseiller, mais on parle d'ensemble « défini par induction », tu peux chercher dans cette direction. Ton exemple de la fonction factorielle (avant que tu édites ton message) était meilleur, d'ailleurs, l'induction étant une théorie plus générale que la récurrence.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte