Micro Systèmes n°25 sep/oct 1982
Micro Systèmes n°25 sep/oct 1982
  • Prix facial : 18 F

  • Parution : n°25 de sep/oct 1982

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (213 x 271) mm

  • Nombre de pages : 246

  • Taille du fichier PDF : 178 Mo

  • Dans ce numéro : dossier sur la peau artificielle et le laser.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 132 - 133  |  Aller à la page   OK
Pages suivantes >
132 133
Les arbres binaires permettent de trier des éléments. Informatique 132 - MICRO-SYSTEMES Une importante caractéristique des arbres est de pouvoir être « parcourus », c'est-à-dire qu'il est possible de se déplacer le long de cette arborescence dans un certain ordre et de traiter les valeurs des noeuds au fur et à mesure de ce parcours. Les trois parcours principaux que l'on peut réaliser sur un arbre se dénomment « préordre », « inordre » et « postordre » et s'expriment de manière très simple  : préordre  : traiter la racine d'abord, les fils ensuite. postordre  : traiter les fils d'abord, la racine ensuite. inordre  : traiter le fils gauche, puis la racine, puis le fils droit. En parcourant successivement une arborescence d'expression arithmétique en préordre, postordre et Mordre on obtient les notations  : préordre  : + * 4 3 * 5 2 (préfixée) postordre  : 4 3 * 5 2 * + (postfixée) inordre  : 4 * 3 + 5 * 2 (infixée) La figure 18 présente une implémentation de ces procédures en Pascal. Il montre la construction d'une arborescence puis son parcours par ces trois algorithmes. Les arbres binaires ont de nombreuses applications en tant que tels. L'une d'entre elles, fort utile, permet de trier des éléments en créant un arbre binaire de recherche. L'algorithme de ce tri revient à créer une arborescence en insérant systématiquement les nombres inférieurs à la racine dans le sousarbre de gauche, et les nombres supérieurs à la racine dans le sousarbre de droite. (fig. 19). Imaginons que la suite des nombres à trier soit  : 12 6 8 92 9 10 36 16 45 108 7... Après insertion de ces nombres dans l'arborescence, on obtient la structure représentée figure 20. Il suffit ensuite d'y appliquer un parcours inordre pour récupérer les nombres triés. Ce type d'algorithme de tri, pour surprenant qu'il soit, est assez rapide et très utilisé dans des tris de table. Revenons aux arborescences program insertion ; type arbre ab t element ; element - record valeur  : integer ; filsg,filsd  : arbre ; end ; var arb  : arbre ; n  : integer ; function inserer (x:integer ; a  : arbre)  : arbre ; begin if a = nil then inserer  : = creer (x,nil,nil) else if x<= at.valeur then inserer  : = inserer(x,at.filsg) else inserer  : = inserer(x,at.filsd) ; end ; begin arb:=nil ; repeat read(n) ; inserer(n,arb) ; until n= 0 ; inordre (arb) ; end. 2.() - L'et:ii de l'Arboresceih:c..pro:,c., nombre:, de 1J suite 12 1, 92/6 16 45 1 OS 7. l n simple parcours inordre sun.it à les relire Septembre-Octobre 1982
Introduction à la programmation structurée Informatique 21. - Repœsentation tin-me d'un arbre binaire.,... peut ci sera utilisée dans le cas où seules deux cellules sont disponibles par nœud de l'arbr Septembre-Octobre 1982 quelconques. Il est possible, comme nous l'avions laissé entendre, de transformer une arborescence quelconque en un arbre binaire, par l'intermédiaire d'une transformation « canonique », c'est-à-dire qui marché dans tous les cas. Cette transformation revient à faire pointer le fils gauche vers le premier des enfants, et le fils droit vers les éléments de même niveau que la racine. Le fils droit se transforme ainsi en frère cadet. Notre arborescence animalière de la figure 17 se traduit donc en un arbre binaire comme le montre la figure 21. Les parcours préordre et postordre ont le même effet que sur un arbre binaire vrai. En revanche, le parcours Mordre produit le comportement suivant  : traiter tous les fils, traiter la racine, traiter tous les frères. Il existe d'autres transformations possibles d'arborescences en arbre binaire. La figure 22 montre une autre formulation de l'arbre zoologique. En réalité, de nombreuses structures plus complexes se réduisent à un arbre binaire. Les listes Lisp, par exemple, sont implantées de cette manière. De même il est possible de représenter un graphe à l'aide d'un arbre binaire. Celui de la figure 23 a été reconverti sous cette forme. Il a été littéralement « éclaté » et redéfini comme la suite des arcs issus des noeuds du graphe. D'autres représentations auraient été possibles. Il est en effet souvent nécessaire d'accomplir un choix quant au mode de représentation, qui tienne compte des besoins, de l'efficacité de l'implantation et des possibilités du langage de programmation dont on dispose. Nous avons ainsi passé en revue quelques-unes des structures de données les plus classiques en informatique. Bien entendu, cette liste n'est pas exhaustive ; des structures plus complexes apparaissent sans cesse, surtout dans les domaines de l'Intelligence Artificielle (réseaux sémantiques, frames, etc.) mais reviennent tou- MICRO-SYSTEMES — 133



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


Micro Systèmes numéro 25 sep/oct 1982 Page 1Micro Systèmes numéro 25 sep/oct 1982 Page 2-3Micro Systèmes numéro 25 sep/oct 1982 Page 4-5Micro Systèmes numéro 25 sep/oct 1982 Page 6-7Micro Systèmes numéro 25 sep/oct 1982 Page 8-9Micro Systèmes numéro 25 sep/oct 1982 Page 10-11Micro Systèmes numéro 25 sep/oct 1982 Page 12-13Micro Systèmes numéro 25 sep/oct 1982 Page 14-15Micro Systèmes numéro 25 sep/oct 1982 Page 16-17Micro Systèmes numéro 25 sep/oct 1982 Page 18-19Micro Systèmes numéro 25 sep/oct 1982 Page 20-21Micro Systèmes numéro 25 sep/oct 1982 Page 22-23Micro Systèmes numéro 25 sep/oct 1982 Page 24-25Micro Systèmes numéro 25 sep/oct 1982 Page 26-27Micro Systèmes numéro 25 sep/oct 1982 Page 28-29Micro Systèmes numéro 25 sep/oct 1982 Page 30-31Micro Systèmes numéro 25 sep/oct 1982 Page 32-33Micro Systèmes numéro 25 sep/oct 1982 Page 34-35Micro Systèmes numéro 25 sep/oct 1982 Page 36-37Micro Systèmes numéro 25 sep/oct 1982 Page 38-39Micro Systèmes numéro 25 sep/oct 1982 Page 40-41Micro Systèmes numéro 25 sep/oct 1982 Page 42-43Micro Systèmes numéro 25 sep/oct 1982 Page 44-45Micro Systèmes numéro 25 sep/oct 1982 Page 46-47Micro Systèmes numéro 25 sep/oct 1982 Page 48-49Micro Systèmes numéro 25 sep/oct 1982 Page 50-51Micro Systèmes numéro 25 sep/oct 1982 Page 52-53Micro Systèmes numéro 25 sep/oct 1982 Page 54-55Micro Systèmes numéro 25 sep/oct 1982 Page 56-57Micro Systèmes numéro 25 sep/oct 1982 Page 58-59Micro Systèmes numéro 25 sep/oct 1982 Page 60-61Micro Systèmes numéro 25 sep/oct 1982 Page 62-63Micro Systèmes numéro 25 sep/oct 1982 Page 64-65Micro Systèmes numéro 25 sep/oct 1982 Page 66-67Micro Systèmes numéro 25 sep/oct 1982 Page 68-69Micro Systèmes numéro 25 sep/oct 1982 Page 70-71Micro Systèmes numéro 25 sep/oct 1982 Page 72-73Micro Systèmes numéro 25 sep/oct 1982 Page 74-75Micro Systèmes numéro 25 sep/oct 1982 Page 76-77Micro Systèmes numéro 25 sep/oct 1982 Page 78-79Micro Systèmes numéro 25 sep/oct 1982 Page 80-81Micro Systèmes numéro 25 sep/oct 1982 Page 82-83Micro Systèmes numéro 25 sep/oct 1982 Page 84-85Micro Systèmes numéro 25 sep/oct 1982 Page 86-87Micro Systèmes numéro 25 sep/oct 1982 Page 88-89Micro Systèmes numéro 25 sep/oct 1982 Page 90-91Micro Systèmes numéro 25 sep/oct 1982 Page 92-93Micro Systèmes numéro 25 sep/oct 1982 Page 94-95Micro Systèmes numéro 25 sep/oct 1982 Page 96-97Micro Systèmes numéro 25 sep/oct 1982 Page 98-99Micro Systèmes numéro 25 sep/oct 1982 Page 100-101Micro Systèmes numéro 25 sep/oct 1982 Page 102-103Micro Systèmes numéro 25 sep/oct 1982 Page 104-105Micro Systèmes numéro 25 sep/oct 1982 Page 106-107Micro Systèmes numéro 25 sep/oct 1982 Page 108-109Micro Systèmes numéro 25 sep/oct 1982 Page 110-111Micro Systèmes numéro 25 sep/oct 1982 Page 112-113Micro Systèmes numéro 25 sep/oct 1982 Page 114-115Micro Systèmes numéro 25 sep/oct 1982 Page 116-117Micro Systèmes numéro 25 sep/oct 1982 Page 118-119Micro Systèmes numéro 25 sep/oct 1982 Page 120-121Micro Systèmes numéro 25 sep/oct 1982 Page 122-123Micro Systèmes numéro 25 sep/oct 1982 Page 124-125Micro Systèmes numéro 25 sep/oct 1982 Page 126-127Micro Systèmes numéro 25 sep/oct 1982 Page 128-129Micro Systèmes numéro 25 sep/oct 1982 Page 130-131Micro Systèmes numéro 25 sep/oct 1982 Page 132-133Micro Systèmes numéro 25 sep/oct 1982 Page 134-135Micro Systèmes numéro 25 sep/oct 1982 Page 136-137Micro Systèmes numéro 25 sep/oct 1982 Page 138-139Micro Systèmes numéro 25 sep/oct 1982 Page 140-141Micro Systèmes numéro 25 sep/oct 1982 Page 142-143Micro Systèmes numéro 25 sep/oct 1982 Page 144-145Micro Systèmes numéro 25 sep/oct 1982 Page 146-147Micro Systèmes numéro 25 sep/oct 1982 Page 148-149Micro Systèmes numéro 25 sep/oct 1982 Page 150-151Micro Systèmes numéro 25 sep/oct 1982 Page 152-153Micro Systèmes numéro 25 sep/oct 1982 Page 154-155Micro Systèmes numéro 25 sep/oct 1982 Page 156-157Micro Systèmes numéro 25 sep/oct 1982 Page 158-159Micro Systèmes numéro 25 sep/oct 1982 Page 160-161Micro Systèmes numéro 25 sep/oct 1982 Page 162-163Micro Systèmes numéro 25 sep/oct 1982 Page 164-165Micro Systèmes numéro 25 sep/oct 1982 Page 166-167Micro Systèmes numéro 25 sep/oct 1982 Page 168-169Micro Systèmes numéro 25 sep/oct 1982 Page 170-171Micro Systèmes numéro 25 sep/oct 1982 Page 172-173Micro Systèmes numéro 25 sep/oct 1982 Page 174-175Micro Systèmes numéro 25 sep/oct 1982 Page 176-177Micro Systèmes numéro 25 sep/oct 1982 Page 178-179Micro Systèmes numéro 25 sep/oct 1982 Page 180-181Micro Systèmes numéro 25 sep/oct 1982 Page 182-183Micro Systèmes numéro 25 sep/oct 1982 Page 184-185Micro Systèmes numéro 25 sep/oct 1982 Page 186-187Micro Systèmes numéro 25 sep/oct 1982 Page 188-189Micro Systèmes numéro 25 sep/oct 1982 Page 190-191Micro Systèmes numéro 25 sep/oct 1982 Page 192-193Micro Systèmes numéro 25 sep/oct 1982 Page 194-195Micro Systèmes numéro 25 sep/oct 1982 Page 196-197Micro Systèmes numéro 25 sep/oct 1982 Page 198-199Micro Systèmes numéro 25 sep/oct 1982 Page 200-201Micro Systèmes numéro 25 sep/oct 1982 Page 202-203Micro Systèmes numéro 25 sep/oct 1982 Page 204-205Micro Systèmes numéro 25 sep/oct 1982 Page 206-207Micro Systèmes numéro 25 sep/oct 1982 Page 208-209Micro Systèmes numéro 25 sep/oct 1982 Page 210-211Micro Systèmes numéro 25 sep/oct 1982 Page 212-213Micro Systèmes numéro 25 sep/oct 1982 Page 214-215Micro Systèmes numéro 25 sep/oct 1982 Page 216-217Micro Systèmes numéro 25 sep/oct 1982 Page 218-219Micro Systèmes numéro 25 sep/oct 1982 Page 220-221Micro Systèmes numéro 25 sep/oct 1982 Page 222-223Micro Systèmes numéro 25 sep/oct 1982 Page 224-225Micro Systèmes numéro 25 sep/oct 1982 Page 226-227Micro Systèmes numéro 25 sep/oct 1982 Page 228-229Micro Systèmes numéro 25 sep/oct 1982 Page 230-231Micro Systèmes numéro 25 sep/oct 1982 Page 232-233Micro Systèmes numéro 25 sep/oct 1982 Page 234-235Micro Systèmes numéro 25 sep/oct 1982 Page 236-237Micro Systèmes numéro 25 sep/oct 1982 Page 238-239Micro Systèmes numéro 25 sep/oct 1982 Page 240-241Micro Systèmes numéro 25 sep/oct 1982 Page 242-243Micro Systèmes numéro 25 sep/oct 1982 Page 244-245Micro Systèmes numéro 25 sep/oct 1982 Page 246