Discussion :

[sandrine]

Bonjour a tous

Je lis les message posté et dans celui sur les algorithmes de tri quelqu'un parle d'arbre or je ne sais pas ce que c'est et à quoi ça sert ainsi que comment on s'en sert

Si quelqu'un a la gentillesse de m'expliquer ca serait sympa

Merci d'avance
A+
sandrine

[jérôme]

Tu vois ce qu'est un arbre dans la nature ?
Un tronc avec des grosses branches, chaque branche ayant elle-même des branches plus petites, qui ont à leur tour des branchilles, puis des feuilles, qui ont des nervures, etc...
Ben là c'est pareil

[GoldenEye]

Par rapport à ton message précédent, un arbre utilise les pointeurs. Je n'ai jamais vu d'arbre programmé sans pointeurs.

[nyal]

loool l explication de jerome. c est tres jolie jerome ( c est un poete du C ).

mais bon c est vrai. c est tres dure à expliquer car il faut connaitre parfaitement toutes les subtilités du langage avant de comprendre les arbres. les arbres, la recursivité c est tres dure à expliquer en quelques lignes (pour ca qu il y a des bouquins la dessus enorme et chiants ).

donc un seul conseil : achete l un de ces livres et lit. je les fais (come la plupart des gens qui font du C). tu vas te rendre compte que c est quelque chose que n utilisera pas tout les jours. De plus les arbres sont couplés avec la recursivité.
Un truc connu est le voyageur de commerce où on doit utiliser le backtracking (sinon tu peux essayer de faire la fonction glob. la fonction de la libc la plus complexe à realiser de loin. chaque shell a d ailleur sa fonction glob)

[Musaran]

Ça sert à organiser des données.

On a un point de départ (racine), duquel partent plusieurs branches vers des noeuds.
Chacun de ces noeuds a, à son tour, des branches vers d'autres noeuds.
En fin de parcours, il y a une feuille à la place d'un noeud, et cette branche cesse de ce ramifier.

Les données peuvent être dans les noeuds et/ou les feuilles.

Par exemple, pour analyser une phrase.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
         _____Phrase______                 <-racine
     ___/  ___/ |  \____  \___________     
    /     /     |       \             \
sujet verbe particule    objet        fin  <-noeuds premier étage
  |     |       |       /     \        |  
  |     |       |  adjectif substantif |   <-noeuds 2ème étage
  |     |       |      |        |      |   
  Tu    as      de    beaux    yeux    .  <-feuilles

[gl]

Les arbres utilises en algo sont assez similaire dans leur representation a l'arbre genealogique, je trouve l'explication de Musaran particulierement claire.

Par rapport à ton message précédent, un arbre utilise les pointeurs. Je n'ai jamais vu d'arbre programmé sans pointeurs.

Si, c'est possible sans pointeur dans certains cas, en utilisabnt entre autre des tableaux. Par exemple pour les arbres binaires, il est assez simple d'utiliser un tableau, la relation entre le pere et ses fils etant : indice_fils_gauche=2*indice_pere+1 et indice_fils_droit=2*indice_pere+2.

[Musaran]

Les pointeurs ne sont jamais qu'un genre d'indice dans la mémoire.

On peut donc toujours le faire dans un tableau, mais il faut une stratégie d'allocation.
C'est même une bonne idée dans certains cas: moins de requêtes système, moins de fragmentation/utilisation de mémoire, ensemble libérable d'un seul coup...
Les conteneurs C++ disposent de la notion d'allocateur pour ça (juste vu, pas essayé).

[mat.M]

les arbres sont similaires aux listes chaînées excepté que la structure qui renfermerait les pointeurs adressant l'occurence suivante et précédente ( dans une liste doublement chaînée ) contient des pointeurs adressant en fait une branche fille gauche et branche fille droite....

typedef struct arbre {

arbre *ptr_branche_gauche ;
arbre *ptr_branche_droite ;
};

Les arbres sont surtout utilisés pour des algorithmes de recherches ou faire des BSP , notamment dans la recherche de faces cachées pour la représentation d'objets 3D

[gl]

les arbres sont similaires aux listes chaînées excepté que la structure qui renfermerait les pointeurs adressant l'occurence suivante et précédente ( dans une liste doublement chaînée ) contient des pointeurs adressant en fait une branche fille gauche et branche fille droite....

typedef struct arbre {

arbre *ptr_branche_gauche ;
arbre *ptr_branche_droite ;
};

D'une part il est possible de faire des arbres sans utiliser de pointeurs comme tu le fais mais en se debrouillant avec des tableaux.
D'autre part ce que tu decris est un cas particulier d'arbre : l'arbre binaire. Il est possible de faire des arbres pouvant contenir N fils.
Pour bien te former la dessus du peux voir les cours algo et les cours de C.