Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arbre - Coggle Diagram
Arbre
Caractéristique
Taille (Nombre de noeud dans un arbre)
Hauteur ( Nombre max de niveau dans l'arbre commençant par 0,1,2...)
Erité (Le nombre de fils dans un arbre)
Qu'est-ce qu'un arbre ?
Il est composé de noeud organisé de manière hierachique
Composition
Racine
Noeud père
Noeud fils
Feuilles
Un noeud sans noeud fils ( généralement vers le bas de l'arbre)
Comment parcourir un arbre ?
En largeur
Etape par étape
En profondeur
Préfixe (Racine,SAG/D)
on prend la racine puis le sous-arbre gauche puis droit ( en allant de gauche puis de droite)
infixe (SAG,Racine,SAD)
Le sous-arbre gauche mais on commence par le bas pour remonter (Gauche puis droite) puis on prend la racine et on fait le sous-arbre droit
postfixe (SAG/D,Racine)
Sous arbre gauche puis droite et enfin la racine
Qu'est-ce qu'un arbre de Recherche ?
Les valeurs sont telles que : Val g < val noeud < val D
La recherche est de complexité O(h) où h=hauteur
Qu'est-ce qu'un arbre binaire ( AB )
Caractéristique d'un AB
Chaque noeud à au max 2 fils
Un AB est complet si tout les niveaux sont rempli sauf le dernier
Un AB est équilibré si chaque noeud à une hauteur qui diffère de 1