Les arbresI. D éfinitionsUn arbre est un ensemble fini de nœud, on distingue un nœud particulier appel é « racine ».Les autres nœuds sont regroup és en n sous ensemble, chacun de ces sous ensemble étant à leur tour un arbre.Père RacineNoeudFilsFeuille Conventions :Les arbres sont toujours repr ésentés la racine en haut et les branches en dessous.Les nœuds extr émité de branches sont des feuilles.On peut d éfinir des liens de parent és entre les nœuds (P ère et fils).On appelle arbre binaire, un arbre dans lequel un p ère à au maximum deux fils.AB GC F HID EOn parle de d égénérescence de l’arbre lorsque tous les successeurs n’appartiennent qu’ à une branche.1358NeoXsysm & DiAboLiK ALGORITHME Pages 1/9erDUT info 1 ann éeUne for êt est un ensemble ordonn é d’arbres. Une for êt peut être consid érés comme un arbre sans racine.NeoXsysm & DiAboLiK ALGORITHME Pages 2/9erDUT info 1 ann éeII. Diff érente forme d’arborescenceA. Arbre g énéalogiqueMarti MireillB. Un questionnairenon ouiQ1 ?non ouiR1Q2 ?R2 R3C. Une hi érarchie Université de LyonLyon 1 Lyon 2 Lyon 3IUT A IUT BD. Un DictionnaireEL TEI E RCRS * ETEE *I**ON*NeoXsysm & DiAboLiK ALGORITHME Pages 3/9erDUT info 1 ann éeE. Expression arithm étique+a*2x cA + (x – c) * 2F. Une PhraseNeoXsysm & DiAboLiK ALGORITHME Pages 4/9erDUT info 1 ann éeIII. Diff érentes repr ésentations d’un arbre binaireO, peut repr ésenté un arbre binaire ...
Un arbre est un ensemble fini de nœud, on distingue un nœud particulier appelé« racine ». Les autres nœuds sont regroupés ennsous ensemble, chacun de ces sous ensembleétantàleur tour un arbre. Père Racine Noeud Fils
Feuille
Conventions:Les arbres sont toujours représentés la racine en haut et les branches en dessous. Les nœuds extrémitéde branches sont des feuilles. On peut définir des liens de parentés entre les nœuds (Père et fils). On appelle arbre binaire, un arbre dans lequel un pèreàau maximum deux fils. A
D
C
B
E
F
G
H
I
On parle de dégénérescence de l’arbre lorsque tous les successeurs n’appartiennent qu’àune branche. 1 3 5 8