arbre binaire de recherche
arbre binaire de recherche
Bonsoir, considérons l'arbre binaire de recherche suivant :
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
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
Dernière modification par GaussX le 02 janv. 2019 22:22, modifié 1 fois.
Re: arbre binaire de recherche
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 ?
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: arbre binaire de recherche
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
Donc tu es d'accord que ton arbre n'est pas un arbre binaire de recherche ?
Professeur de maths MP Lycée Sainte-Geneviève
Re: arbre binaire de recherche
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.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: arbre binaire de recherche
oui ,j'avoue que j'étais à coté . Ta définition est correcte Errys, merci de ta réponse.