Discussion :

[dword2add]

Bonjour,

J'ai une question sur les arbres de recherches :
Je considère l'arbre suivant :
....A
.. /..\
.B....C

On peut aussi l'écrire avec la notation "parenthèse gauche" :
A(B,C)

Mais si je considère l'arbre A(B), je me retrouve avec 2 possibilités :

....A.................A
.../.........ou .......\
.B.......................B

Ces deux arbres sont ils identiques ? si non comment les différencier ?


Merci

PS. Pour la notation "parenthèse gauche" je sais pas si ca se dit en francais...
PS Les ... sont juste là pour faire les indentations car le html a l'air dêtre interdit...

[Jedai]

PS Les ... sont juste là pour faire les indentations car le html a l'air dêtre interdit...

Tu peux utiliser les balises CODE (avec le bouton # de l'interface du forum) pour conserver l'indentation.

Les deux arbres sont différents, et certains parcours (infixe) de l'arbre donneront des résultats différents sur les deux versions.
A(B,()) ou A((),B) me semblerait des notations plus saines.

--
Jedaï

[dword2add]

Le parcours infixe c'est preorder ?
Donc si on inverse deux branches (gauche et droite) c'est plus le même arbre ?

[Trap D]

Le parcours infixe c'est preorder ?
Donc si on inverse deux branches (gauche et droite) c'est plus le même arbre ?

Non, mais celà dépend du sens qui est donné à cet arbre.
Si c'est un arbre de recherche exemple avec une liste de nombres rangée dans un arbre, il est évident que

Code :

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

1
2
3
4
5
 
  1
 / \
/   \
2   4

n'a pas la même signification que

Code :

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

1
2
3
4
5
 
  1
 / \
/   \
4   2

Maintenant si les noeuds sont des villes voisines, l'ordre des noeuds n'a plus d'importance.

[dword2add]

En fait ca épend des usages, ca m'embête carje dois dire si la notation de type A(B,A(D)) décrit un arbre de manière unique.

[Jedai]

En fait ca épend des usages, ca m'embête carje dois dire si la notation de type A(B,A(D)) décrit un arbre de manière unique.

La réponse est oui et non. Un arbre dans l'absolu oui, un arbre binaire non. Si on parle d'un arbre binaire, à strictement parler, un noeud a toujours 2 fils et une feuille 0. Un arbre au sens mathématique n'est qu'un graphe pointé sans cycle et un noeud peut avoir 0,1 ou plusieurs fils.

Dans ton message originel, tu parles d'arbre de recherches, les arbres de recherches sont binaires et l'ordre des fils y est significatif, dans ce cas A(B,A(D)) est ambigu.

--
Jedaï