Pointeurs et références (Arbres binaires)

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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

Éternel curieux

+0 -0

Cette réponse a aidé l'auteur du sujet

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

Édité par mehdidou99

Plus on apprend, et, euh… Plus on apprend. | Coliru, parfait pour tester ses codes sources !

+1 -0
Auteur du sujet

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…

Édité par Ozmox

Éternel curieux

+0 -0

Cette réponse a aidé l'auteur du sujet

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

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+2 -0

Cette réponse a aidé l'auteur du sujet

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.

+1 -0

Cette réponse a aidé l'auteur du sujet

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

Édité par blo yhg

+1 -0
Staff

Cette réponse a aidé l'auteur du sujet

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.

Édité par nohar

I was a llama before it was cool

+2 -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.

+1 -0

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
Auteur du sujet

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!

Éternel curieux

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

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.

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+2 -0
Auteur du sujet

Bonjour! Je déterre mais j'ai enfin un peu de temps libre pour ces artifices!

Petite question : Est-ce qu'on utilise les arbres binaires en mathématiques? Est-ce qu'on peut les considérer comme des ensembles ordonnés (ou pas)?

Édité par Ozmox

Éternel curieux

+0 -0

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 ?

Édité par anonyme

+0 -0
Auteur du sujet

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.

Édité par Ozmox

Éternel curieux

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

+0 -0
Auteur du sujet

Merci, j'ai trouvé quelques documents. Je vais pas aller trop loin mais je pense que j'ai une bonne base pour en sortir quelques petits trucs. C'est agréable aussi, de faire un peu de recherche comme ça. :-)

Édité par Ozmox

Éternel curieux

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

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