Les Arbres binaires de recherche (ABR)151018145 1457 12 181015 7 12 5 7 10 12 14 15 181 2 3 4 5 6 7Un arbre binaire de recherche est un arbre ordonn é, on le lit g énéralement de droite à gauche.127 155 1014 18I. Appartenance d’un élément à l’ABRA. Principe On compare la valeur cherch ée à la racine Si elles sont égales, l’algorithme est termin é Si la racine est plus grande que le nombre, on recherche à gauche Si la racine est inf érieure au nombre, on recherche à droiteNeoXsysm & DiAboLiK ALGORITHME Pages 1/7erDUT info 1 ann éeB. AlgorithmeFonction logique appartient (x, racine)Val TIND xVal NŒUD *racineDébutSi racine = NULLAlorsRetourne FauxSinonSi x = (*racine).infoAlorsRetourne vraiSinonSi x < (*racine).infoAlorsRetourne (appartient(x, (*racine).gauche))SinonRetourne (appartient(x, (*racine).droite))FinsiFinsiFinsiFinII. Parcours d’un ABRIl s’agit d’un parcours infix é d’arbre.(Voir chapitre pr écédent).III. Insertion dans un ABRA. PrincipeL’algorithme se d écompose en deux parties : Trouver la place de l’insertion Insertion de l’ élémentNeoXsysm & DiAboLiK ALGORITHME Pages 2/7erDUT info 1 ann éeB. AlgorithmeProcédure inserabr (racine, elem)Val NŒUD *racineVal TIND elemVar localesNŒUD *adresseDébutAdresse place (racine, elem)Insert (elem, adresse)FinFonction NŒUD *place(racine, elem)Val NŒUD *racineVal TIND elemDébutSi (elem < (*racine).info) et ((*racine) ...
Un arbre binaire de recherche est un arbre ordonné, on le lit généralement de droiteàgauche. 12
7
15
5 110418
I. Appartenanced’unélémentàl’ABR A. Principe - Oncompare la valeur cherchéeàla racine - Sielles sontégales, l’algorithme est terminé - Sila racine est plus grande que le nombre, on rechercheàgauche - Sila racine est inférieure au nombre, on rechercheàdroite