Définitions récursives associées aux arbres
Arbre enraciné.
L'ensemble d'arbres enracinés, où un arbre enraciné est constitué d'un ensemble de sommets contenant un sommet distingué appelé racine, et d'arêtes reliant ces sommets, peut être défini de manière récursive par les étapes suivantes:
- Cas de base : Un seul sommet r est un arbre enraciné.
- Etape récursive : Supposons que T1, T2,. . . , Tn sont des arbres à racines disjointes avec des racines r1, r2,. . . , rn, respectivement. Ensuite, le graphe formé en commençant par une racine r, qui ne se trouve dans aucun des arbres enracinés T1, T2,. . . , Tn, et l’ajout d’une arête de r à chacun des sommets r1, r2, ..., rn est également un arbre enraciné.
L'ensemble des arbres binaires étendus.
L'ensemble des arbres binaires étendus peut être défini de manière récursive par les étapes suivantes:
- Cas de base : l'ensembe vide est un arbre binaire étendu..
- Etape récursive : Si T1 et T2 sont des arbres binaires étendus disjoints, il existe un arbre binaire étendu, noté T1 · T2, constitué d’une racine r avec des arêtes reliant la racine à chacune des racines du sous-arbre gauche T1 et sous-arbre droit T2 lorsque ces arbres ne sont pas vides.
Arbres binaires complets .
L'ensemble des arbres binaires complets peut être défini de manière récursive par les étapes suivantes:
- Cas de base : Il existe un arbre binaire complet constitué d’un seul sommet r.
- Etape récursive : Si T1 et T2 sont des arbres binaires complets disjoints, il existe un arbre binaire complet, noté T1 · T2, constitué d’une racine r avec des arêtes reliant la racine à chacune des racines du sous-arbre gauche T1 et sous-arbre droit T2.
Hauteur d'un arbre .
Nous définissons la hauteur h(T) d'un arbre binaire complet T de manière récursive par les étapes suivantes:
- Cas de base : La hauteur de l’arbre binaire complet T constitué d'un seul sommet r est h(T)=0.
- Etape récursive : Si T1 et T2 sont des arbres binaires complets, l’arbre binaire complet T = T1 · T2 a la hauteur h(T) = 1 + max (h (T1), h (T2)).
Nombre de sommets dans un arbre binaire complet .
Si nous prenons n(T) le nombre de sommets dans un arbre binaire complet, Nous définissons n(T) de manière récursive par les étapes suivantes :
- Cas de base : Le nombre de sommets n(T) de l’arbre binaire complet T constitué uniquement d’une racine r est n(T) = 1.
- Etape récursive : Si T1 et T2 sont des arbres binaires complets, le nombre de sommets de l’arbre binaire complet T = T1 · T2 est n(T) = 1 + n(T1) + n(T2).
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
