parcours unique d'un arbre binaire

[invite5a9a6b90]

bonjour,
j'ai une démonstration en algorithmique élémentaire dont je n'arrive pas à trouver la solution.Voici l'enoncé :
On suppose que P et I sont des listes telles que :
(pi1) les éléments de P sont deux à deux distincts
(pi2) P et I ont la même longueur et sont composées des mêmes éléments.
Montrer que ,s'il existe un arbre binaire dont le parcours préfixe est P et le parcours infixe est I alors cet arbre est unique
Indication : ce résultat peut se démontrer par l'absurde pour la partie inductive en utilisant une récurrence sur la longueur de la liste P

Je reste bloqué malgré l'indication donnée

merci d'avance de l'aide que vous m'apporterez
-----

[invite5a9a6b90]

nobody can help me ?

[invite67660fe3]

Bonjour,

Je reconnais parfaitement le sujet que vos enseignants de TD vous ont donnés il y a quelques jours. Vous aviez une semaine entière pour résoudre celui-ci, et visiblement, vous ne vous êtes intéressé au sujet que très récemment. J'annoncerai donc lors du prochain cours en amphithéâtre la nullité de ce devoir si une réponse est apportée sur ce forum.

Sur ce, bonnes révisions, et à la semaine prochaine.

[invite179e6258]

elle est bien bonne celle-là. Je parie que c'est du bluff.

[A voir en vidéo sur Futura]

[inviteb6b93040]

Bonjour,

L'arbre existe quand l'ordre de I est l'inverse de celui de P
Il ne peut en exister d'autres car il n'y a qu'une solution pour inverser l'ordre
L'absurde ne m'a pas servie alors peut être que pas la bonne démo
Votre avis ?