arbre binaire de recherche

Modérateur : Michel Quercia

Répondre
GaussX
Messages : 272
Enregistré le : dim. janv. 24, 2016 9:20 pm

arbre binaire de recherche

Message par GaussX » mer. janv. 02, 2019 10:12 pm

Bonsoir, considérons l'arbre binaire de recherche suivant :
arbre recherche.png
arbre recherche.png (12.91 Kio) Vu 917 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
Modifié en dernier par GaussX le mer. janv. 02, 2019 11:22 pm, modifié 1 fois.

Errys
Messages : 300
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: arbre binaire de recherche

Message par Errys » mer. janv. 02, 2019 10:14 pm

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-2018
LLG MP*3 2019-2020

GaussX
Messages : 272
Enregistré le : dim. janv. 24, 2016 9:20 pm

Re: arbre binaire de recherche

Message par GaussX » mer. janv. 02, 2019 11:24 pm

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.

JeanN
Messages : 5311
Enregistré le : dim. sept. 04, 2005 7:27 pm
Localisation : Versailles

Re: arbre binaire de recherche

Message par JeanN » jeu. janv. 03, 2019 12:37 am

GaussX a écrit :
mer. janv. 02, 2019 11:24 pm
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 MPSI Lycée Sainte-Geneviève

Errys
Messages : 300
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: arbre binaire de recherche

Message par Errys » jeu. janv. 03, 2019 1:04 am

GaussX a écrit :
mer. janv. 02, 2019 11:24 pm
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-2018
LLG MP*3 2019-2020

GaussX
Messages : 272
Enregistré le : dim. janv. 24, 2016 9:20 pm

Re: arbre binaire de recherche

Message par GaussX » jeu. janv. 03, 2019 11:17 pm

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

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Exabot [Bot] et 2 invités