arbre binaire de recherche

Répondre

Messages : 286

Enregistré le : 24 janv. 2016 20:20

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) Vu 4461 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 02 janv. 2019 22:22, modifié 1 fois.

Messages : 317

Enregistré le : 04 oct. 2017 15:58

Classe : MP

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

Messages : 286

Enregistré le : 24 janv. 2016 20:20

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 : 5506

Enregistré le : 04 sept. 2005 19:27

Localisation : Versailles

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 MPSI Lycée Sainte-Geneviève

Messages : 317

Enregistré le : 04 oct. 2017 15:58

Classe : MP

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

Messages : 286

Enregistré le : 24 janv. 2016 20:20

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