Page 1  sur  1

arbre binaire de recherche

Posté : 02 janv. 2019 21:12
par GaussX
Bonsoir, considérons l'arbre binaire de recherche suivant :
arbre recherche.png
arbre recherche.png (12.91 Kio) Vu 4485 fois


j'ai trouvé dans un bouquin que le parcours infixe d'un arbre binaire de recherche donne une séquence des valeurs de l'arbre dans l'ordre croissant. Pour l'arbre ci-dessus la séquence après parcours infixe est : 20 30 50 60 40 70 80 qui ne suit pas un ordre croissant , me suis-je trompé ?

Merci de votre aide

Re: arbre binaire de recherche

Posté : 02 janv. 2019 21:14
par Errys
Bonjour, ton parcours infixe est correct, c'est l'arbre que tu as donné qui n'est pas un arbre binaire de recherche. Quelle est la condition que doit vérifier un arbre binaire de recherche ?

Re: arbre binaire de recherche

Posté : 02 janv. 2019 22:24
par GaussX
Bonsoir Errys et merci de ta réponse, un arbre binaire de recherche est un arbre binaire qui vérifie :la valeur de tout fils gauche est inférieure à la valeur du nœud et la valeur de tout fils droit est supérieure à la valeur du nœud.

Re: arbre binaire de recherche

Posté : 02 janv. 2019 23:37
par JeanN
GaussX a écrit :
02 janv. 2019 22:24
Bonsoir Errys et merci de ta réponse, un arbre binaire de recherche est un arbre binaire qui vérifie :la valeur de tout fils gauche est inférieure à la valeur du nœud et la valeur de tout fils droit est supérieure à la valeur du nœud.
Donc tu es d'accord que ton arbre n'est pas un arbre binaire de recherche ?

Re: arbre binaire de recherche

Posté : 03 janv. 2019 00:04
par Errys
GaussX a écrit :
02 janv. 2019 22:24
Bonsoir Errys et merci de ta réponse, un arbre binaire de recherche est un arbre binaire qui vérifie :la valeur de tout fils gauche est inférieure à la valeur du nœud et la valeur de tout fils droit est supérieure à la valeur du nœud.
C'est ça. En revanche, ta formulation "la valeur de tout fils gauche" pourrait laisser penser que tu parles uniquement DU fils gauche d'un noeud, et pas du sous-arbre de gauche en entier. Ainsi, tu pourrais dire "la valeur d'un noeud est supérieure à la valeur de tout noeud de son sous-arbre de gauche et inférieure à la valeur de tout noeud de son sous-arbre de droite."
Qui prête moins à confusion à mon goût.

Re: arbre binaire de recherche

Posté : 03 janv. 2019 22:17
par GaussX
oui ,j'avoue que j'étais à coté . Ta définition est correcte Errys, merci de ta réponse.