Les arbres en pascal

Résumé du document

Ceci est un TD sur les arbres et structures de données dynamiques utilisées en algorithmique et en Pascal.
Basées sur la notion particulière des pointeurs et variables dynamiques et appuyé par des schémas explicites.
L'application de tels arbres voit son utilisation dans les notations préfixés ou postfixées inhérentes aux types de parcours de ces arbres et incluant le concept de récursivité.

Extraits

[...] Arbres : C'est un graphe orienté défini sur un ensemble de nœuds X tel que : il existe dans X un nœud particulier r appelé la racine de l'arbre. les autres nœuds , s'il en existe, sont partitionnés en m sous-ensembles X1,X2, ,Xm , qui sont à leur tour des arbres de racines respectives r1,r2, tels que pour tout i de 1 à m il existe un arc d'origine r et d'extrémité ri .Ces arbres sont appelés les sous-arbres de X. [...]

[...] 07/06/200508:19:43 Pour les révisions des étudiants, par les soins de Klouche-Djedid A Département Informatique-IGMO + _ * B C / _ A 2 D 5 soit A 2 B + C * D / Parcours en largeur : rarement appliqué, il consiste à examiner les nœuds par niveaux successifs, de gauche à droite. Son application sur fig4 donne + - * B C / A 2 D 5 Algorithmes de parcours Afin de définir ces algorithmes, sans tenir compte de la représentation de l'arbre, nous utiliserons les fonctions suivantes : EXISTEG(X) : fonction booléenne, retourne la valeur vrai si le sous-arbre gauche du nœud X transmis en entrée existe. EXISTED(X) : fonction booléenne, retourne la valeur vrai si le sous-arbre droit du nœud X transmis en entrée existe. [...]

[...] 07/06/200508:19:43 Pour les révisions des étudiants, par les soins de Klouche-Djedid A Département Informatique-IGMO soit + - A 2 B * C / D 5 dans cette forme d'écriture de l'expression, l'opérateur précède le(s) opérande(s) qui lui sont associé(s). Les parenthèses ne sont pas utilisées puisque les opérateurs apparaissent dans l'ordre de leur exécution. Cette écriture est appelée notation polonaise préfixée parcours post-ordre :aussi appelé post-fixé ou terminal, il consiste à examiner les fils avant le père en commençant par le fils gauche. Pour chaque sous-arbre les 3 étapes s'exécutent dans l'ordre suivant : parcours du sous-arbre gauche, parcours du sous-arbre droit, examen du père. [...]

[...] Le parcours du sous-arbre gauche d'un nœud X est réalisé par la procédure PG définie ci-dessous. procedure PPI (racine) procedure PG(X) debut debut X racine EXAMINER(X) PG(X) EMPILER repeter tant que EXISTEG(X) DEPILER(X) faire si EXISTED(X) X GAUCHE(X) alors EXAMINER(X) X DROITE(X) EMPILER(X) PG(X) finfaire fsi fin PG jusqu'à VIDE(P) fin PPI Procédure parcours postordre récursif :PTR procedure PTR(racine) debut si EXISTEG (racine) alors PTR( GAUCHE (racine)) fsi si EXISTED (racine) alors PTR( DROITE (racine fsi EXAMINER(racine) fin Procédure parcours symétrique récursif :PSR procedure PSR(racine) debut si EXISTEG (racine) alors PSR( GAUCHE (racine)) fsi EXAMINER(racine) si EXISTED (racine) alors PSR( DROITE (racine fsi fin réalisé pour le site web www.nardjess-web.gratishost.com par Klouche-Djedid A. [...]

[...] L'arbre représentant l'expression est le suivant : C réalisé pour le site web www.nardjess-web.gratishost.com par Klouche-Djedid A. 07/06/200508:19:43 Pour les révisions des étudiants, par les soins de Klouche-Djedid A Département Informatique-IGMO + _ * B C / _ A 2 D 5 fig4 Parcours d'arbre binaire parcourir un arbre consiste à examiner une fois et une seule chacun de ses nœuds , dans un certain ordre. pour un arbre binaire les ordres de parcours les plus utilsés sont : parcours pré-ordre : Il est aussi appelé préfixé ;dans cet ordre de parcours le père est examiné avant les fils. [...]