arbre binaire de recherche

Messages : 0

Inscription : 24 janv. 2016 20:20

Profil de l'utilisateur : Élève de lycée

arbre binaire de recherche

Message par GaussX » 02 janv. 2019 21:12

Bonsoir, considérons l'arbre binaire de recherche suivant :
arbre recherche.png
arbre recherche.png (12.91 Kio) Consulté 5266 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
Dernière modification par GaussX le 02 janv. 2019 22:22, modifié 1 fois.

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: arbre binaire de recherche

Message par Errys » 02 janv. 2019 21:14

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-?

Messages : 0

Inscription : 24 janv. 2016 20:20

Profil de l'utilisateur : Élève de lycée

Re: arbre binaire de recherche

Message par GaussX » 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.

Messages : 3901

Inscription : 04 sept. 2005 19:27

Profil de l'utilisateur : Élève de lycée

Re: arbre binaire de recherche

Message par JeanN » 02 janv. 2019 23:37

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 ?
Professeur de maths MP Lycée Sainte-Geneviève

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: arbre binaire de recherche

Message par Errys » 03 janv. 2019 00:04

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.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?

Messages : 0

Inscription : 24 janv. 2016 20:20

Profil de l'utilisateur : Élève de lycée

Re: arbre binaire de recherche

Message par GaussX » 03 janv. 2019 22:17

oui ,j'avoue que j'étais à coté . Ta définition est correcte Errys, merci de ta réponse.

Répondre