Parcours suffixe / prefixe / infixe

[MacErmite]

Bonjour à tous,

je révise actuellement des notions d'informatiques et notamment les différents modes de parcours sur des arborescences. J'en ai fait un, peut être un peut trop compliqué, du coup je ne sais plus trop comment faire.




Pour un parcours prefixe j'ai trouvé ceci : 1,2,6,14,18,19,7,15,8,3,9,10,16,17,20,21,22,4,11,12,5,13

mais je ne trouve pas pour un parcours suffixe et infixe :doh:

De plus, pouvez-vous me dire l'interet de ces demarches ? (je suis novice en informatique)

Merci

[eusebius]

Est-ce que tu es sûr que les définitions que tu as, notamment pour le parcours infixe, ne sont pas pour des arbres binaires ?

Sinon pour l'intérêt de la chose, le premier truc auquel je pense c'est l'interprétation et l'évaluation d'une expression logique ou arithmétique.

Par exemple :
plus(a,plus(b,c))
(a,(b,c)plus )plus
(a plus (b plus c))
sont respectivement les notations préfixée, postfixée et infixée d'un même arbre, que tu n'auras pas de mal à reconstruire (mais que moi ça me broute de dessiner avec des caractères).

Pour un parcours infixe, il suffit de prendre récursivement :
[sous-arbre gauche], racine, [sous-arbre droit]
En fait c'est la notation standard des expressions logiques et arithmétiques : (a + b), (a + (b * c))...
Tu vois je pense pourquoi ma définition marche mal avec des arbres non binaires... Mais peut-être qu'on t'en a donné une plus générale.

Pour un parcours suffixe :
[sous-arbre gauche], [sous-arbre droit], racine
mais là on peut généraliser :
[sous-arbre 1]...[sous-arbre n], racine
Du coup on peut le faire pour ton exemple.
Si on le fait pas à pas (à chaque étape, je simplifie l'expression entre crochets la plus à gauche) :

• [arbre de racine 2][arbre de racine 3][arbre de racine 4][arbre de racine 5], 1
• [arbre de racine 6][arbre de racine 7], 8, 2, [arbre de racine 3][arbre de racine 4][arbre de racine 5], 1
• [arbre de racine 14], 6, [arbre de racine 7], 8, 2, [arbre de racine 3][arbre de racine 4][arbre de racine 5], 1
• 18, 19, 14, 6, [arbre de racine 7], 8, 2, [arbre de racine 3][arbre de racine 4][arbre de racine 5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, [arbre de racine 3][arbre de racine 4][arbre de racine 5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, 9, [ar10], 3, [ar4],[ar5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, 9, 16, [ar17], 10, 3, [ar4], [ar5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, 9, 16, 20, 21, 22, 17, 10, 3, [ar4], [ar5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, 9, 16, 20, 21, 22, 17, 10, 3, 11, 12, 4, [ar5], 1
• 18, 19, 14, 6, 15, 7, 8, 2, 9, 16, 20, 21, 22, 17, 10, 3, 11, 12, 4, 13, 5, 1

Voilà, si je n'ai pas fait d'erreur la dernière ligne doit être ton parcours suffixe.

[MacErmite]

Pour le parcours infixe j'ai relevé ce chemin :
18,14,19,6,2,15,7,8,1,9,3,16,10,20,17,21,22,11,4,12,5,13

[eusebius]

Pour le parcurs infixe j'ai relevé ce chemin :
18,14,19,6,2,15,7,8,1,9,3,16,10,20,17,21,22,11,4,12,5,13

En généralisant comme ça la formule que j'ai donnée, alors... OK.
[sous-arbre 1], racine, [sous-arbre 2]... [sous-arbre n]

[MacErmite]

Le cours que j'ai parle de la structure d'un ordinateur (mémoire rom, ram, disque dur, bus...) et il y a juste une illustration avec un noeud et une feuille à droite et à gauche (enfin je crois que cela s'appelle ainsi, car c'est juste écrit 1,2,3 dans des cercles !) et l'on doit donner des parcours sur des forets entières :ptdr: . Je trouve cela plus que limite pour des cours !

Du coup je ne sais pas ou cela va me mener de me promener dans cette foret :doh: