Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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 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 M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :