Chap v les arbres de recherche

Diabolik

Description

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) ...

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: frerovic
• Nombre de lectures: 236
• Langue: Français

Extrait

Les Arbres binaires de recherche (ABR) 15 10

18 14 5 14 5 7 1218 10 15 712 5 7 10 12 14 15 18 1 23 4 5 67

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

NeoXsysm & DiAboLiK er DUT info 1année

ALGORITHME

Pages 1/7