[PDF] Apprendre à programmer les arbres en langage C - Première partie





Previous PDF Next PDF



TP 8 : Arbres binaires de recherche

Ajouter des typedef pour définir les nouveaux types noeud_t et arbre_t (ces types devraient permettre de représenter une feuille c'est à dire un arbre vide).



Parcours dun arbre binaire

ordre infixe : ch



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



Un analogue du monoïde plaxique pour les arbres binaires de

binaires de recherche tournoi) T (? ) associé à une permutation ? ? Sn. C'est un arbre binaire (incomplet) à n sommets numérotés de 1 à n.



Un analogue du monoïde plaxique pour les arbres binaires de

binaires de recherche tournoi) T (? ) associé à une permutation ? ? Sn. C'est un arbre binaire (incomplet) à n sommets numérotés de 1 à n.



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



Structures de données Avancée

Les arbres binaires de recherche. — Ce type d'arbre il y a une cohérence entre les nœuds



Les arbres binaires de recherche équilibrés

Un nœud est une feuille si ses deux fils sont vides sinon c'est un nœud La propriété d'arbre binaire de recherche permet de trouver



Programmation avancée Projet 2: Arbre binaire de recherche

Nov 7 2014 associées `a chacun des mots dans l'arbre binaire de recherche. L'arbre binaire de ... C'est `a dire



1 ALGORITHMES ET COMPLEXITÉ

RECHERCHE. Définition. Arbre binaire tel qu'en tout nœud la recherche de l'élément de clé c dans l'arbre a. Elt recherche (c CCle; a ABR; e Elt).



ARBRES BINAIRES DE RECHERCHE - Université de Montréal

A l’aide d’un arbre de recherche on peut impl` ementer une table de symboles d’une´ maniere tr` es ef?cace ` Operations :´ recherche d’une valeur particuliere` insertion ou suppression d’une valeur recherche de min ou max et des autres Pour la discussion des arbres binaires de recherche on va considerer les pointeurs´



Apprendre à programmer les arbres en langage C - Première partie

Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé telle que • chaque nœud du sous-arbre gauche possède une clé inférieure ou égale à celle du nœud considéré • chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci



ARBRES BINAIRES DE RECHERCHE - Université de Montréal

Dans un arbre binaire de recherche chaque nœud a une cle ´ Acces aux nœuds :` gauche(x) etdroit(x) pour les enfants de x (nulls’il n’y en a pas) parent(x) pour le parent de x (nullpour la racine) cle(x) pour la cle de nœud´ x (en gen´ eral un entier dans nos discussions)´



Exercice 1 : Arbre binaire de recherche (15 points) - CNRS

Exercice 1 : Arbre binaire de recherche (15 points) Dans cet exercice nous nous intéressons aux arbres binaires de recherche (ABR) Pour rappel dans un ABR tous les éléments dans le fils gauche d’un nœud sont plus petits que ce nœud et tous les éléments à droite sont plus grands (cf Annexe pour les fonctions membres de la classe Arbre)



Arbres binaires de recherche [br] Algorithmique - Unisciel

Un arbre binaire de recherche (abr eg e ABR) est un arbre binaire v eri ant la propri et e suivante : soient x et y deux noeuds de l’arbre : • Si y est un noeud du sous-arbre gauche de x alors cle(y) ? cle(x) • Si y est un noeud du sous-arbre droit de x alors cle(y) ? cle(x) Exemple

Quelle est la valeur qui décide du lieu d'insertion dans un arbre binaire ?

Le premier élément est inséré à la racine de l'arbre, l'élément suivant est inséré à gauche si la valeur de sa clé est inférieure à celle de la racine et à droite si la valeur de sa clé est supérieure à celle de la racine (on aurait pu faire l'inverse).

Comment comparer deux arbres binaires ?

affiche_arbre2_rec ( arbre ); printf (" " ); } Exercice 7 Écrire une fonction compare() qui compare deux arbres binaires (la fonction renvoie une alveur nulle si et seulement si les deux arbres binaires ont la même structure d'arbre et qu'ils portent les mêmes aleursv aux n÷uds se correspondant).

Quels sont les avantages d'une calculatrice en arbre binaire ?

C'est là son gros avantage par rapport aux listes chaînées. Il est souvent bien plus rapide de parcourir l'arbre de la racine jusqu'à une feuille, plutôt qu'une longue liste chaînée parfois entièrement.

Comment les arbres binaires sont-ils semblables aux listes chaînées?

Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'où leur nom (on pourrait très bien voir une liste chaînée comme un arbre à une seule branche). Il est courant d'appeler le premier élément d'un arbre la racine.

Cours 4 : Les arbres binaires

Définition

Implémentation

Manipulation

Définition

Un arbre binaire est un arbre qui

possède au maximum deux sous-arbres (d"où le binaire)

2013-2014 Algorithmique2

Deux implémentations

possibles

Version itérative•Un arbre binaire est constitué de noeuds•Chaque noeud " pointe » vers deux noeuds de l"étage inférieur

Version récursive•Un arbre binaire peut être vide•Un arbre binaire possède un noeud (étiqueté ou pas)•Un arbre binaire possède deux sous-arbres " fils »

2013-2014 Algorithmique3

Utilisation

Enormément d"applications, que ce soit

dans le domaine informatique ou pas :•Expressions mathématiques : 3 + 2*5 - 4 4 3 2 5

2013-2014 Algorithmique4

Autres exemples

Résultats d"un tournoi à élimination

directe (tennis par exemple)Arborescence de si-alors-sinon(voir les arbres de décision pour les tris vus à la première séance)

2013-2014 Algorithmique5

Un peu de vocabulaire

Un arbre est constitué de

noeuds (ou sommets

Ces sommets sont reliés par des

arcs (ou arêtes ) orientés : père ®fils

Il existe dans tout arbre un noeud qui

n"est le point d"arrivée d"aucun arc : c"est la racine

2013-2014 Algorithmique6

Un peu de vocabulaire (2)

Tout autre noeud est la racine d"un

sous-arbre de l"arbre principalUn noeud qui n"est le point de départ d"aucun arc est appelé feuille

Pour les arbres binaires, on distinguera

de façon visuelle le fils gauche du fils droit

2013-2014 Algorithmique7

Un exemple

racine feuilles sommets 4 3 2 5

2013-2014 Algorithmique8

Un exemple

sous-arbre gauche de "-» 4 3 2

5sous-arbre droit de "-»

2013-2014 Algorithmique9

Un peu de vocabulaire (3)

La hauteur d"un noeud est la longueur du plus long chemin de ce noeud aux feuilles qui en dépendent plus 1 •C"est le nombre de noeuds du chemin •La hauteur d"un arbre est la hauteur de sa racine

•L"arbre vide a une hauteur 0 •L"arbre réduit à une racine étiqueté a une hauteur 1

2013-2014 Algorithmique10

Un peu de vocabulaire (4)

La profondeur d"un noeud est le nombre de noeuds du chemin qui va de la racine à ce noeud

•La racine d"un arbre est à une profondeur 0 •La profondeur d"un noeud est égale à la profondeur de son père plus 1 •Si un noeud est à une profondeurp, tous ses fils

sont à une profondeurp+1 Tous les noeuds d"un arbre de même profondeur sont au même niveau

2013-2014 Algorithmique11

Premier traitement sur un

arbre L"affichageTrois façons d"afficher •Préfixe•Infixe•Postfixe

2013-2014 Algorithmique12

Affichages

Préfixe :•On affiche la racine, puis le sous-arbre gauche, puis le sous-arbre droit Infixe :•On affiche le sous-arbre gauche, puis la racine, puis le sous-arbre droit Postfixe :•On affiche le sous-arbre gauche, puis le sous-arbre droit, puis la racine

2013-2014 Algorithmique13

1 3 2 4 5 6

Un exemple

2013-2014 Algorithmique14

Résultats

Préfixe :•1 2 4 3 5 6

Infixe :•4 2 1 5 6 3

Postfixe•4 2 6 5 3 1

2013-2014 Algorithmique15

Deuxième traitement

Recherche d"un élémentAu moins deux façons de faire :•DFS :

Depth-First Search

ou recherche en profondeur d"abord •BFS :

Breadth-First Search

ou recherche en largeur d"abord

2013-2014 Algorithmique16

DFS en détail

DFS :•On cherche à la racine•S"il n"y est pas :•On cherche dans le fils gauche•Puis s"il n"était pas dans le fils gauche, on cherche

dans le fils droit

Idée : explorer à fond chaque branche avant de passer à la suivanteOn s"arrête quand on a trouvé ou qu"il n"y a plus de branches à explorer

2013-2014 Algorithmique17

Réflexions

On reconnaît encore une fois un

fonctionnement récursifProblème : si l"élément est dans le sous arbre droit de la racine, on va quand même explorer tout le sous-arbre de gauche

2013-2014 Algorithmique18

Exemples

1 3 2 4 5 7 6

2013-2014 Algorithmique19

Avec DFS : on cherche 4

Racine = 1 ®non•On explore le fils gauche•Racine = 2 ®non•On explore le fils gauche-Racine = 4 ®TROUVÉ

2013-2014 Algorithmique20

Avec DFS (2) : on cherche 3Racine = 1 ®non•On explore le fils gauche•Racine = 2 ®non•On explore le fils gauche-Racine = 4 ®non-Pas de fils

•Pas de fils droit •On explore le fils droit•Racine = 3 ®TROUVÉ

2013-2014 Algorithmique21

BFS en détail

BFS :•On cherche à la racine•Si l"élément n"y est pas :•On cherche dans les noeuds de profondeur 1•S"il n"est pas dans à la profondeur 1, on cherche à la profondeur 2•Etc...

2013-2014 Algorithmique22

Réflexions

Plutôt un fonctionnement itératifOn va avoir besoin d"une file FIFO (ou autre structure équivalente) pour

stocker les noeuds à explorer :•On ne peut pas " sauter » d"un noeud de profondeur pà un autre•Il faut se souvenir de la liste des noeuds à traiter

2013-2014 Algorithmique23

Fonctionnement de la file

Au début, la file contient l"arbre principalSi la valeur n"est pas à la racine du premier arbre de la file•On supprime l"arbre de la file•On ajoute ses deux sous-arbre en fin de file s"ils ne sont pas vides•Et on explore l"arbre suivant, qui est le premier de la file

On s"arrête quand on a trouvé ou que la file est vide

2013-2014 Algorithmique24

Exemples

1 3 2 4 5 7 6

2013-2014 Algorithmique25

Avec BFS : on cherche 3

File = [arbre " 1 »]Valeur de la racine = 1 ®nonOn enlève l"arbre " 1 »et on ajoute ses deux

sous-arbres•File = [sous-arbre gauche de " 1 », sous-arbre

droit de " 1 »]•On explore le premier : racine = 2 ®non•On l"enlève et on ajoute ses sous-arbres•File= [sous-arbre droit de " 1 », sous-arbre gauche de

" 2 »]•On explore le premier : racine = 3 ®TROUVÉ

2013-2014 Algorithmique26

Avec BFS (2) : on cherche 4File = [arbre " 1 »]Valeur de la racine = 1 ®nonOn enlève l" arbre " 1 »et on ajoute ses deux sous-arbres•File = [s.-a. gauche de " 1 », s.-a. droit de " 1 »]•On explore le premier : racine = 2 ®non•On l"enlève et on ajoute ses deux sous-arbres•File = [s.-a. droit de " 1 », s.-a. gauche de " 2 »]•On explore le premier : racine = 3 ®non•On l"enlève et on ajoute ses deux sous-arbres-File = [s.-a. gauche de " 2 », s.-a. gauche de " 3 », s.-a. droit de " 3 »]-On explore le premier : racine = 4 ®TROUVÉ

2013-2014 Algorithmique27

Comparatif

Avec DFS, on n"a besoin d"aucun

stockage en plus mais on peut s"attarder trop longtemps dans une brancheAvec BFS, on fonctionne par profondeur incrémentale donc on évite le piège mais on a besoin d"un stockage dont la taille augmente à chaque étape

2013-2014 Algorithmique28

Les ABR

On voit que la recherche dans les

arbres binaires est peu aiséeAutre problème: où ajouterun élément?Solution : les ABR ou arbres binaires de

recherche

2013-2014 Algorithmique29

Définition

Un arbre binaire de recherche (ABR est un arbre binairedans lequel chaque noeud possède une clételle que •chaque noeud du sous-arbre gauche possède une clé inférieure ou égale à celle du noeud considéré•chaque noeud du sous-arbre droitpossède

une clé supérieure ou égale à celle-ci •(on pourra interdire ou non des clés de valeur égale)

2013-2014 Algorithmique30

Pourquoi les problèmes

sont-ils réglés ?

Pour la recherche : à partir de la racine,

on sait si on doit explorer le fils gauche ou le fils droit •DFS devient très efficace

Pour l"ajout, le nouveau noeud ajouté

devient une feuille•Ici aussi il suffit de faire une DFS en descendant systématiquement à droite ou à gauche suivant qu"on est inférieur ou supérieur à la racine

2013-2014 Algorithmique31

Et si on veut supprimer

un noeud ? Si c"est une feuille•Facile, rien à faire•On garde un ABR Sinon si c"est un noeud avec un seul s.-a.•On le remplace par son sous-arbre

Sinon•On lui donne la valeur minimale de son sous-arbre droit et on supprime ce noeud (récursif)

2013-2014 Algorithmique32

Exemple

3 6 2 1 4 7 5

On supprime 52013-2014 Algorithmique33

On supprime 5

3 6 2 1 4 7

2013-2014 Algorithmique34

Exemple

3 6 2 1 4 7 5

On supprime 22013-2014 Algorithmique35

On supprime 2

3 6 1 4 7 5

2013-2014 Algorithmique36

Exemple

3 6 2 1 4 7 5

On supprime 32013-2014 Algorithmique37

On supprime 3

3 6 2 1 4 7 5 4 6 2 1 4 7 5 4 6 2 1 5 7 4 6 2 1 5 7

2013-2014 Algorithmique38

quotesdbs_dbs5.pdfusesText_10
[PDF] les arbres en c openclassroom

[PDF] arbre binaire de recherche algorithme

[PDF] arbre binaire de recherche algorithme suppression

[PDF] parcours en profondeur arbre

[PDF] arbre binaire complet

[PDF] dénombrement cours

[PDF] arbre de probabilité pile ou face

[PDF] arbre de probabilité seconde

[PDF] arbre probabilité conditionnelle

[PDF] arbre de décision exercices corrigés

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart