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 : 130 - 131  |  Aller à la page   OK
Pages suivantes >
130 131
Tout arbre peut se ramener à un arbre binaire. Informatique 4 3 5 2 Fig. lb. - Les arborescences peuvent représenter la syntaxe d'une expression arithmétique. autorisent une manipulation dans les deux sens, alors que les listes circulaires (b) renden égaux » les éléments en supprimant le caractère particulier des têtes de listes. bre de situations et de phénomènes  : décomposition d'un programme en sous-programme, arbre d'évaluation d'un jeu de stratégie (échec, dames, etc.), syntaxe d'une expression arithmétique (fig. 16) ou d'un langage de programmation, classement divers, tel qu'un classement zoologique en espèces, genres, variétés, etc. (fig. 17). Les arborescences sont ainsi utilisées dans de nombreux domaines de l'informatique  : compila- tion, conception de systèmes d'exploitation, Intelligence Artificielle, architectures de bases de données, etc. Signalons qu'un arbre se définit formellement (et récursivement) de la manière suivante  : on appelle arbre de type T une structure de données de même type, que l'on dénomme racine, et d'une suite d'arbres de même type, que l'on dénomme sous-arbres ; cette suite pouvant être nulle. A l'image d'un arbre généalogique, on appelle « noeuds fils » les noeuds issus de la racine, et « noeud père » la racine d'un sous-arbre. Les arborescences quelconques n'ont pas de représentation physique directement appropriée. Afin de pouvoir implanter cette struc- ANIMAL I MAMMIFERE I V OISEAIJ I REPTILE MOLLUSQUE I INSECTE r I I, CHIEN [SINGE r-Huuri Fig 17. - Un classement zoologique qui suit une approche hiérarchique peut se forMuler sous la forme d'une arboreçeem 130 - MICRO-SYSTEMES Septembre-Octobre 1982
Introduction à la programmation structurée Informatique ture, nous allons analyser une arborescence d'un type particulier  : l'arbre binaire, qui se représente directement en machine. De plus, on verra que tout arbre peut se ramener à un arbre binaire. Un arbre binaire est un arbre dont chaque noeud ne possède que deux branches, et pour lequel on fait une différence entre le filsgauche et le fils-droit. Autrement dit un arbre de la forme/\B C sera différent de/A\C B Une telle restriction est en fait un avantage car, lorsque nous traiterons d'arborescences quelconques, nous donnerons un caractère différent aux branches selon qu'elles sont à droite ou à gauche. Un arbre binaire se définit logiquement par les opérations suivantes  : • Accès qui se différencie en trois fonctions  : — racine, qui lit la racine d'un arbre, — droite qui lit la branche droite d'un arbre, — gauche qui donne accès au sous-arbre gauche.• construction  : création d'un arbre binaire à partir de deux sous-arbres et d'une racine.• test  : fonction vide qui détermine si un sous-arbre est vide ou non. Il existe deux représentations physiques possibles d'un arbre binaire  : utilisation de tableaux ou d'agrégats. Implanté sous forme de tableaux, la structure d'un arbre binaire se réduit à trois vecteurs. Le vecteur des valeurs, qui porte la composante significative d'un noeud, le vecteur des pointeurs sur les fils gauches et le vecteur des pointeurs sur les fils droits. L'autre forme, qui emploie la notion d'agrégat, est très utilisée en Pastal. program expression ; type arbre = t element ; element = record valeur filsg filsd end ; var expr  : arbre ; char ; arbre ; arbre ; function creer(v:char ; fg,fd:arbre):arbre ; var p:arbre ; begin new(p) ; pt.valeur:=v ; pt.filsg:=fg ; pt.filsd:=fd ; creer:=p ; end ; procedure preordre(a:arbre) ; begin if a nil then begin write(at.valeur) ; preordre(at.filsg) ; preordre(at.filsd) ; end ; end ; procedure postordre (a:arbre) ; begin if a<>nil then begin postordre(at.filsg) ; postordre(al.filsd) ; write(at.valeur) ; end ; end ; procedure inordre (a:arbre) ; begin if a<> nil then begin inordre(af.filsg) ; write(al.valeur) ; inordre(at.filsd) ; end ; end ; begin (m programme principal x) expr:= creer ('+',creer creer('4',nil,nil), creer('3',nil,ni1)), creer ('x', creer('5',nil,nil), creer('2',nil,ni1))) ; preordre(expr) ; writeln ; postordre(expr) ; writeln ; inordre(expr) ; end. Septembre-Octobre 1982 MICRO-SYSTEMES — 131



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