Chapitre 1 - Arbres binaires de recherche PDF

TP 8 : Arbres binaires de recherche

noeud_t et arbre_t (ces types devraient permettre de représenter une feuille c'est à dire un arbre vide). ? Correction typedef struct noeud_s {.

Algorithmes dans les arbres binaires [tn03] - Exercices

Écrivez une classe TNoeudBinaire<T> qui représente un noeud d'un arbre binaire d'éléments de type T. Validez votre classe avec la solution. Solution C++.

ARBRES BINAIRES DE RECHERCHE

Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...

Chapitre 1 - Arbres binaires de recherche

arbre de le représenter avec la tête en bas

INF601 : Algorithme et Structure de données - Cours 2 : TDA Arbre

27 févr. 2010 INF601 : Algorithme et Structure de données. Introduction. Organisation d'un arbre binaire a b c d e g f racine sous arbre Gauche.

Arbres et récursivité

1 juil. 2020 un arbre binaire c'est beaucoup plus compliqué

Conception de structures de données Pourquoi les arbres

Un arbre binaire est une structure permettant de stocker une collection de données de même type. Définition d'un arbre binaire en C arbre vide:.

Parcours darbres Préfixe : 1 2

ARBRES BINAIRES DE RECHERCHE

Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...

[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam

Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d'un arbre binaire contenant une valeur entière Ajouter des typedef pour

[PDF] Cours 4 : Les arbres binaires

Un arbre binaire est constitué de nœuds • Chaque nœud « pointe » vers deux nœuds de l'étage inférieur ?Version récursive • Un arbre binaire peut être

[PDF] Algorithmique Les arbres

Tout arbre binaire de n nœuds possède 2n branches Plus précisément lorsque n ? 1 il possède n ? 1 branches internes et n + 1 branches externes

[PDF] Les arbres - Ecole Mohammadia dIngénieurs-Cours

Dans ce qui suit on traitera les arbres binaires (degré=2) C'est le type le plus basique dont toutes les opérations sont valables pour un arbre n-aire

[PDF] Les arbres binaires de recherche - Zeste de Savoir

12 août 2019 · à créer une structure de données révolutionnaire : les arbres binaires de recherche Qu'est-ce que c'est à quoi ça sert comment ça marche

[PDF] Parcours dun arbre binaire

ordre infixe : chaidl jrkeb f 1 2 Seconde définition des trois parcours Dans la balade schématisée plus haut on ajoute les fils fantômes

[PDF] Structures de données et algorithmes

conventionnel et il est basé sur un arbre de recherche binaire sont liés par cette relation par exemple les nœuds B et C ne sont pas reliés

Les structures de données arbres en langage C - Academiaedu

Les structures de données arbres en langage C Download Free PDF Un arbre binaire est un cas basique: les algorithmes de manipulation d'un tel arbre

[PDF] CH2 ARBRES - IGM

9 IMAC ch 2 17 Propriétés : - un arbre binaire de hauteur n a au plus 2n+1 – 1 noeuds dont 2n noeuds externes - le nombre de feuilles est égal à un de

[PDF] Cours 4 et 5 Les arbres 1 Introduction 11 Définition Larbre est une

C:\ Program Files Send To Norton Word Excel Eudora Word nav exe Word98 exe Définition : un arbre binaire est un arbre dont les nœuds ont au plus

Comment creer un arbre binaire en C ?
Pour faire des arbres en C, tu peux utiliser les structures et les pointeurs. Un peu comme les listes chaînées. Une branche représenté par un pointeur et donc chaque nœud de ton arbre peut être représenter par deux pointeurs.
Comment coder un arbre binaire ?
La taille d'un arbre binaire non vide vaut : 1 + taille(sous-arbre gauche) + taille(sous-arbre droit). La hauteur d'un arbre binaire non vide vaut : 1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit)).
Quelle est la complexité dans le pire cas de la recherche d'un élément dans un arbre binaire de recherche de hauteur H contenant n nœuds ?
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une clé dans un arbre binaire de recherche équilibré est donc O(log2(n)).
Un arbre binaire de recherche (ABR) est un arbre binaire qui a la propriété suivante : quelque soit le nœud p = <x, G, D>, les nœuds appartenant `a son sous-arbre gauche G ont des valeurs strictement inférieures `a x, et les nœuds appartenant son sous-arbre droit D ont des valeurs supérieures ou égales x.

Chapitre1

Arbresbinairesderec herche

1 Lesarbre sonttr`esuti lis´eseni nformatique,d'un epartparcequeles informationssontsouventhi´erarch is´ees,e tpeuventˆetrerepr´ esent´eesnaturel- lementsousuneformearb orescente ,etd'autre part,parceque lesstructures dedonn´ eesarborescentespermet tentdestockerdesdonn´eesvolumineu ses defa¸con queleuracc`es soite ffi cace.

1.1Quelques exemplesdedonn´eesarb orescentes

Expressionsarithm´etiques.Onpeut repr´esenter lesexpressionsarith- m´etiquespardesar bres´etiq uet´espardesop´erateurs,desconstantesetdes variables.Las tru cturedel'arbrerendcomptedela priorit ´edesop´erateurs etrend inutiletoutp arenth´esage. 2 75/
y t x z

1.Cech apitrere prendenquasitotalit´e lechapitredemˆe menomfi gurantdanslepoly -

copi´educoursd'Algo rithmi quedesL2d'in formatiqueetdemath´ematiquesdel'universit´ e d'AixMarseille,r´ edig´eparF.Denis,S.Grandc olasetY.Vax`es. 1

2CHAPITRE1.ARBRESBINAIRES DE RECHERCHE

Exercice: Dessinezl'arbrecorrespondan t`al'expression3(2x-1)+1. Arbressyntaxiques. Unarbresyntaxi querepr´esentel'analysed'une phrase`apartird'u nense mbleder`eglesqui constituelagrammaire:une phraseestcompos´e ed'ungroupenominalsuivid'un groupeverbal,ungrou pe nominalpeut-ˆetre constitu´ed'unarticleetd'unnomcom mun,... livre groupe nominal verbecomplément phrase articlenom commun articlenom commun lechatlit le groupe verbal Arbresg´en´ealogique s.Unarbreg´en´ealogi que(descendantdansle caspr´e sent)repr´esenteladescendan ced'unepersonneoud'uncouple.Les noeudsdel'arbresont ´etiqu et´esparlesmembres delafamill eetleurs conjoints.L'arborescenceestc onstruite`apartirdesliensdeparent´ e(les enfantsducouple).

LucieMattéo

Paul

Victor

Naomi

Ginette

Georges

LillyTom

LéonMélanieThéo

Arbrelexicographiq ue.Unarbrelexicogra phique,ouar br eenparties communes,oudictionnaire,rep r´e senteunensembledemots.Lespr´efixes communs`aplusieurs motsappar aissentuneseulefoisdansl'arbre ,cequi setradu itparungaind'espacem´ emoire. Deplu slarec herched'unmotest asseze ffi cace,puisqu' ilsu ffi tde parcouri runebranchedel'arbreen partant 1.2.D

EFINITIONSETTERMINOLOGIE3

delarac ine,en cherchant`achaqueni veauparm ilesfilsdunoeudcourant lalett redumotderangcorresp ondant. e e l t re o t i ls m a e i p ic ne male mie mite pic pile pis port porte main

Exercice: Rajoutezlemotmal.

1.2D´efinit ionsetterminologie

D´efinition.Unarb reestunensem bleorganis´ edenoe udsdanslequel chaquenoeudaunp`ereetunse ul,sau funnoeudquel'onap pellelaracine. Sileno eudpestle p`ere dunoeudf,nou sdironsque festun filsdep,et sileno eudpn'apasdefi lsnousd ironsqu ec'estune feuille.Ch aquenoeud porteune´etiquetteouvaleuroucl´e.On al'habi tud e,lorsqu'ondessineun arbre,delerepr´e sente ravecl atˆeteenbas,c'est-`a-direquelaracinees ttout enhaut, etlesnoeudsfi lssont repr´esen t´esen-dessousduno eudp`ere. racine feuilles

4CHAPITRE1.ARBRESBINAIRES DE RECHERCHE

Unno eudestd´efinipar son´etiquetteetsessous-arbres.On peutd onc repr´esenterunarbreparunn-uplet?e,a 1 ,...,a k ?danslesque leestl' ´etiquette port´eeparlenoeud,e ta 1 ,...,a k sontsessous -arbres.Par exemplel'arbre correspondant`al'expressionarithm´ etique (y/2-t)×(75+z)serarepr´esent´e par ?×,?-,?/,?y?,?2??,?t??,?+,?75?,?z??? Ondist inguelesarbresbinairesdesarbresg ´en´eraux.Leurpar ticula- rit´eestqueles filssontsin gularis´es :chaquenoe udaunfilsgau cheetun filsdroit. L'uncommel'autrepe utˆetreu narbrevide,qu el'onnotera??. L'´ecritured'unarbres'entrouvemo difi´ee,puis qu'unnoeudat oujoursdeux fils.Enrepren antl'ex pressionarithm´etiquepr´e c´edente,l'arbrebinairequi larepr´ esentes'´ecrit Onutil isepourlesarbresuneter minologiein spir´eede sliensdeparent´ e: -lesdescendantsd'unno eudpsontlesno eudsquiapp araissentdans sessous-arb res, -unancˆetred'unnoeud pestsoitson p`ere,soit unancˆe tredesonp`ere, -lechem inquirelieunnoeud `alaracin eestconstitu´ede tousses ancˆetres(c'est-`a-direde sonp`ereetdesnoeudsducheminquirelie sonp`er e`alaracine), -unfr`ered'unno eudpestun filsdup `erede p,et quin'e stpasp. hauteur=5 descendant ancetre niveaux profondeur=2 noeud de degré 3 racine frère chemin à la racine Lesnoeu dsd'unarbreser´epar tissentparniveaux:le premie rniveau (parconvent ionceseraleniveau0)contient laracin eseulement, ledeux i`eme 1.2.D

EFINITIONSETTERMINOLOGIE5

niveaucontientles deuxfilsdelaracine,... ,lesnoeu dsduniveauksontles filsdesno eudsduniv eauk-1,....Lahauteurd'unarbreestl enombrede niveauxdesesnoeuds .C'est doncaussil enombredenoeudsquijalonn ent labranc helapluslongue.Atte ntion,l ad´efinitiond elahauteurvariee n fonctiondesauteurs.P ourcertains lahauteurd'unarbreconte nantunseu l noeudest0. Arbresbinaires:haute ur,nombredenoeudsetnom bre de feuilles. Unarb rebinaireestcompletsitoute ssesbranchesontl amˆemelongu eur ettouss esnoeudsq uinesontp asdesfeuillesontdeux fils.SoitAunarbre binairecomplet.Lenombr edenoeudsdeAauni veau0est1,lenombr ede noeudsauniveau1est2, ... ,etlenombredeno eud sauniveaupestdonc 2 p .En particu lierlenombredefeuillesestdonc2 h-1 sihestlenombr ede niveaux. 16 8 4 2 1 racine nombre de noeuds Lenom bretotaldenoeudsd 'unarbreb inairec ompletdehniveauxest h-1 i=0 2 i =2 h -1 Onend´ eduitq uelahauteurht(A)(l enombreden iveaux)d'unarbre binaireAcontenantnnoeudsestaumoins´egal e`a ?log 2 n?+1 Preuve.SiAestarbrede hauteurhetcompor tantnnoeuds,pourtout m-1 .Par contrapos ´ee,ona:n≥2 m-1 h≥m.Lep lus grandentiermv´ erifiantn≥2 m-1 est?log 2 n?+1.O na donch≥?log 2 n?+1.

6CHAPITRE1.ARBRESBINAIRES DE RECHERCHE

Exercice: Montrezquepourtoutent iern≥1,?log

2 n?+1=?log 2 (n+ 1)?.

Lahau teurminimale?log

2 n?+1e stat teintelors quel'arbreestcom- plet.Pourˆetree ffi caces,lesalgorithm esquiutil isentdesarbresbinairesfont ensorte queceuxcisoie nt´equil ibr´es(voirle stasoul esAVL-arbrespar exemple). Lesarbres enth´eoriedesgraph es.Enth´e oriedesgraphesunarbre estungraphe connexeetsanscycles,c' est-`a-direqu'entredeuxsommets quelconquesdugrapheilexisteunche minetu nseul.Onparl edansce casd'arb renonplant´e,puisqu 'iln'y apasdesommetparticulier quijoue lerˆole deracine.Less ommetss ontvoisinslesunsdes autres, iln'yapas dehi´e rarchiequipermetdedirequ'unsom metestlep `ere(oulefils)d'un autresommet.On d´emontrequ'ungraphe densommetsquiacetteprop ri´et´e contientexactementn-1arˆ etes,etquel'ajoutd'un enouvel learˆetecr ´eeun cycle,tandisqueler etraitd'unearˆet elerendnon connexe .

1.3Arbres binaires

Lesarbresbinaires(AB)formen tunestructurededonn ´eesquip eutˆetre d´efinier´ecursivement delamani`eresuivante:unarbrebinaireest -soitvide, -soitcompos´ ed'uneracineportantun e´etiquette(cl ´e)etd'unepaire d'arbresbinaires,appel´ esfilsgaucheetdroit. Pourpouvoirm anipulerdesarbre sderecherche,ondoitdoncdis poser desfoncti onnalit´essuivantes: -bool´een:estvide(ABa):un efonctionq uitestesiunarbreest videounon, -AB:fils gauche(ABa)etAB:fils droit(ABa),de sfonctions quiretourn entlesfilsgaucheetdroitd'unarbr enonvide, -CLE:val(AB a),un efonctionq uiretournel'´etique ttedelar acine d'unarbrenonv ide, -ABcreearbrevide(),un efonctionq uicr´eeunarbrevide, -ABcreearbre(CLEv,AB fg,fd),un efonctionqu icr´eeunarbre dontlesfils gaucheetdroi tsontfgetfdetdontl aracinees t´etiq uet´ee parv -changeval(CLEv,AB a),un efonctionq uiremplacel'´etique ttede laracin edeaparv,siaestnonvide ,etnef aitriensinon -changefg(ABfg,AB a)etchangefd(ABfd,AB a),de sfonctions quiremplac entlefilsgauchedea(resp.lefilsdroitdea)par fg(resp.

1.3.ARBRE SBINAIRES7

parfd),si aestnonvide ,etnef ontriensinon. EnConut il ise eng´en´eraldespointeur spourre pr´esenterlesliensentre unnoeu detsesfilsdansun arbrebi naire. EnPyth on,onpeutrepr´esent eru narbrevideparu nelistevide[]etun arbrenonvidepar unelis tecomprenant3 ´el´em ents[cl´e,filsgauche,filsdroit]. 14 7 12

916782

11 1 Parcoursd'unarbrebinai re.Lepar coursleplussimple` aprogramm er estleparcou rsditenpr ofondeurd'abord.Son princi peestsimple:pour parcourirunarbrenonvidea,onp arc ourtr´ecursivements onsous-arbre gauche,puissonsous -arbredroit,la racine del'arbrepouvantˆetretrait´ ee aud´ ebut,entrelesdeuxparc oursou`alafin.Dans lepremier cas,ondit quelesnoe udssonttrai t´esdansunordrepr´efixe,dan slesecond cas,dans unordre infixeetdansl etroisi`e mecas,s elonunordrepostfixe.

Parcours(ABa)

siNONest_vide(a)

Traitement_prefixe(val(a))

Parcours(fils_gauche(a))

Traitement_infixe(val(a))

Parcours(fils_droit(a))

Traitement_postfixe(val(a))

L'a ffi chagedes´e tiquettes desnoeudsd'unarbrebinairepeutsefair e dansunordre pr´efix e,infixeoupost fixe.Pourl'arbreci-dessus, una ffi chage pr´efixedonnerait:12191677 8261.

8CHAPITRE1.ARBRESBINAIRES DE RECHERCHE

Affichage_pr´efixe(ABa)