Algorithmique Les arbres
Algorithme. Entrée : un entier positif ou nul n. Sortie : une liste d'arbres res <- listeVide() si n = 0 alors ajoute(res arbreVide()) retourner res.
Arbres binaires de recherche [br] Algorithmique
Introduction. Un arbre binaire de recherche est une structure de donnée qui permet de représen- ter un ensemble de valeurs si l'on dispose d'une relation
Structures de données et algorithmes
Ici A est la racine. ? Les nœuds qui ne possèdent pas de fils sont appelés feuille de l'arbre. Les feuilles de l'
Cours 4 et 5 Les arbres 1. Introduction 1.1. Définition Larbre est une
IUT De Villetaneuse. Année 2004-2005. Dépt informatique. 2éme Année. F. Lévy - Algorithmique avancée. Page 1/17. Cours 4 et 5. Cours 4 et 5. Les arbres. 1.
Arbres - Algorithmique 1
Arbres : définition 1. Un arbre est un ensemble organisé de noeuds : ? chaque noeud a un père et un seul. ? excepté un noeud
Cours Algorithmique avancée (WI)
? Un arbre binaire est un arbre où chaque nœud est connecté à deux sous-arbres. (un sous-arbre gauche et un sous arbre droit). ?C'est un arbre de degré 2 c'
INF601 : Algorithme et Structure de données - Cours 2 : TDA Arbre
Feb 27 2010 INF601 : Algorithme et Structure de données. Introduction. Arbres Binaires. Définition informelle. Dans un arbre binaire tout noeud a au ...
Arbres pour lalgorithmique
Dec 12 2018 arbres en analyse d'algorithmes. Prérequis. Une familiarité avec les outils mathématiques de base (niveau L2) est sou- haitable.
Algorithmes et structures de données : TD 1 Corrigé - Arbres binaires
Par contre cet arbre est ni parfait ni dégénéré. 4. Afficher cet arbre binaire de la mani`ere préfix
Parcours dun arbre binaire
En-dessous : infixe. 2 Algorithmes récursifs. Pour chacun des parcours définis ci-dessus (postfixe infixe
Complexit´e asymptotique
Rappel :
SetLength(tableau, n)est de complexit´e O(n)
SetLength(tableau, 1)est de complexit´e O(1)
New(element)est de complexit´e O(1) quandelementest d"un type de taille fixeExercice 1.1Arbres binaires
Consid´erer l"arbre suivant :
1. D´essiner cet arbre.
2. Quelle est la hauteur de l"arbre ?
La hauteur de l"arbre est 3.
3. Est-ce que cet arbre est un arbre entier, un arbre parfait (=complet), et/ou un arbre
d´eg´en´er´e ? Cet arbre est entier car chaque noued a zero ou deux fils. Par contre, cet arbre est ni parfait ni d´eg´en´er´e.4. Afficher cet arbre binaire de la mani`ere pr´efix, puis infix,et ensuite postfix.
Premi`erement, on va afficher cet arbre sans utiliser des parentheses.Pr´efix* + 3 / 4 2 - 8 * 2 3
Infix3 + 4 / 2 * 8 - 2 * 3
Postfix3 4 2 / + 8 2 3 * - *
Deuxi`emement, on va afficher cet arbre en utilisant des parentheses. Notez que les par- enth`eses sont important uniquement pour la notationinfix. Pr´efix*( +( 3, /( 4, 2) ) , -( 8, *( 2, 3) ) )Infix( ( 3+ ( 4/2 ) ) * ( 8- ( 2*3 ) ) )
Postfix( ( 3, ( 4, 2)/)+, ( 8, ( 2, 3)*)-)*
5. Consid´erer la fonction suivante :
procedure afficher( noeud : p_t_noeud ) d´ebut si NOT(noeud^.gauche = NIL) alors afficher(noeud^.gauche) si NOT(noeud^.droite = NIL)alors afficher(noeud^.droite)Write(noeud^.contenu);
fin6. Faites tourner l"appelafficher(racine);avec laracinede votre arbre dans un tableau.
Utiliser une nouvelle colonnenoeud^ .contenupour chaque nouvelle variable locale. noeudˆ .contenu noeudˆ .contenunoeudˆ .contenunoeudˆ .contenu1er appel
2`eme appel3`eme appel4`eme appel
*+3/ noeudˆ .contenu noeudˆ .contenunoeudˆ .contenunoeudˆ .contenu5`eme appel
6`eme appel7`eme appel8`eme appel
42-8noeudˆ .contenu noeudˆ .contenunoeudˆ .contenu
9`eme appel
10`eme appel11`eme appel
*237. Que fait cette proc´edure ?
Cette proc´edure affiche l"arbre de la mani`ere postfix.3 4 2 / + , 8, 2, 3 * -
8. Ecrire une fonction d´efinie par r´ecurrence qui calcule le r´esultat du terme d´ecrit par cet
arbre binaire. (D´emarche : Quelle est la condition d"arrˆet ? Comment faut-il placer les appels
r´ecurrents ?) function calculer ( noeud : p_t_noeud ) : integer; d´ebut si (noeud^.contenu = "+") alors result := calculer(noeud^.gauche) + calculer(noeud^.droite) sinon (noeud^.contenu = "-") alors result := calculer(noeud^.gauche) - calculer(noeud^.droite) sinon (noeud^.contenu = "*") alors 2 result := calculer(noeud^.gauche) * calculer(noeud^.droite) sinon (noeud^.contenu = "/") alors result := calculer(noeud^.gauche) / calculer(noeud^.droite) sinon result := StrToInt(noeud^.contenu); fin si fin L"´evaluation du terme donne le r´esultat 10, bien evidemmment.Exercice 1.2Arbres binaire de recherche
Consid´erer l"ensemble des cl´es 1,4,5,10,16,17,21.1. Dessiner des arbres binaires de recherche de cet ensemblede cl´es avec une hauteur de 3,
puis 5, et ensuite 7. 3Exercice 1.3Arbres binaire de recherche
1. Etablir la structure de donn´eesp
tnoeudpour cet arbre binaire de recherche contenant une cl´e (integer) et deux pointeurs, un pour le sous-arbre gauche, et un pour le sous-arbre droite. type p_t_noeud = ^t_noeud; t_noeud = RECORD cle : integer; gauche : p_t_noeud; droite : p_t_noeud; END;2. Ecrire une fonctionfunction max(noeud : p
tnoeud ):integerqui calcule le maxi- mum de l"abre de recherche. function max(noeud : p_t_noeud) : integer; var temp : p_t_noeud; var max : integer; begin max := Low(Integer); { Le plus faible possible } temp := noeud; while NOT(noeud = NIL) do begin if noeud^.cle > max then max := noeud^.cle ; noeud := noeud^.droite; end; result := max; end;3. Ecrire une fonctionfunction min(noeud : p
tnoeud ):integerqui calcule le mini- mum de l"abre de recherche. function min(noeud : p_t_noeud) : integer; var temp : p_t_noeud; var min : integer; begin min := High(Integer); { Le plus grand possible } temp := noeud; while NOT(noeud = NIL) do begin if noeud^.cle < min then min := noeud^.cle ; noeud := noeud^.droite; end; result := min; end; 4quotesdbs_dbs46.pdfusesText_46[PDF] les arbres rouges de maurice vlaminck
[PDF] les arenes de nimes
[PDF] les arguments de créon pour convaincre antigone
[PDF] les arguments de la dérive des continents
[PDF] lES ARGUMENTS DE WEGENER
[PDF] Les arguments envers les Incas-Espagnols
[PDF] les arguments et les exemples
[PDF] Les arméniens pendant la 1ere Guerre Mondiale
[PDF] Les Armes sont-elles nécessaire
[PDF] Les arrondis au centième et millimètre près
[PDF] les articles en espagnol pdf
[PDF] Les articles indefinis
[PDF] Les artificiers DM
[PDF] les artificiers sont cachés du public par un mur de hauteur 2m