Les arbres comme un type spécial de graphes

2.1 Composants principaux d'un arbre

Arbre — c'est un type spécial de graphe qui est acyclique et connexe. Dans un arbre, il existe un seul chemin entre n'importe quelle paire de nœuds, ce qui rend sa structure hiérarchique.

Composants principaux d'un arbre :

1. Nœuds :

• Les principaux éléments de l'arbre qui contiennent des données.
• Par exemple, chaque cercle dans le diagramme représente un nœud.

2. Racine :

• Un nœud qui n'a pas de nœuds parents. Il est le point de départ de l'arbre.
• Par exemple, le nœud supérieur dans le diagramme.

3. Feuilles :

• Des nœuds qui n'ont pas de nœuds enfants. Ils se trouvent aux "extrémités" de l'arbre.
• Par exemple, les nœuds en bas du diagramme.

4. Arêtes :

• Les connexions entre les nœuds. Elles définissent les relations parent-enfant entre les nœuds.
• Par exemple, les lignes reliant les nœuds dans le diagramme.

5. Sous-arbres :

• Tout sous-ensemble de l'arbre, composé d'un nœud et de tous ses descendants.
• Par exemple, une branche de l'arbre partant d'un nœud.

Caractéristiques importantes d'un arbre :

1. Hauteur de l'arbre :

• La longueur du chemin de la racine à la feuille la plus éloignée.
• Par exemple, le nombre de niveaux dans le diagramme.

2. Profondeur d'un nœud :

• La longueur du chemin de la racine à ce nœud.
• Par exemple, le nombre de niveaux de la racine à un nœud donné.

2.2 Arbres binaires

On peut distinguer différents types d'arbres. Commençons par les plus simples.

Arbre binaire — c'est un arbre dans lequel chaque nœud a au plus deux nœuds enfants, appelés les descendants gauche et droit.

Exemple d'arbre binaire :

Types particuliers d'arbres binaires :

Arbre binaire complet :

Tous les niveaux de l'arbre, sauf le dernier, sont entièrement remplis, et tous les nœuds du dernier niveau sont placés le plus à gauche possible.

Arbre binaire parfait :

Tous les nœuds internes ont exactement deux nœuds enfants, et toutes les feuilles se trouvent au même niveau.

Arbre binaire équilibré :

La différence de hauteurs des sous-arbres de n'importe quel nœud ne dépasse pas 1.

Arbre binaire de recherche :

Pour n'importe quel nœud, son sous-arbre gauche ne contient que des nœuds avec des valeurs inférieures, et le sous-arbre droit – uniquement des nœuds avec des valeurs supérieures.

2.3 Arbres n-aires

Un arbre n-aire est un arbre dans lequel chaque nœud peut avoir au plus n nœuds enfants.

Types particuliers d'arbres n-aires :

1. Arbre ternaire (Ternary Tree) :

Chaque nœud a au plus trois nœuds enfants.

2. Arbre k-aire (k-ary Tree) :

Chaque nœud a au plus k nœuds enfants.

Exemple d'arbre 3-aire (chaque nœud a au plus trois nœuds enfants) :

2.4 Exemples d'utilisation des arbres

1. Système de fichiers

Utilisation des arbres : Représentation de la structure hiérarchique des fichiers et dossiers dans un système d'exploitation.

Le nœud racine représente le répertoire racine, les nœuds internes — les dossiers, et les feuilles — les fichiers. Les opérations incluent la création, la suppression et le déplacement des fichiers et dossiers.

2. Arbre de décision

Utilisation des arbres : Analyse et apprentissage automatique pour la prise de décision.

Les nœuds internes représentent les questions ou conditions, les branches — les réponses possibles, et les feuilles — les décisions ou actions finales. Par exemple, le diagnostic de maladies en médecine basé sur les symptômes.

3. Document XML/HTML

Utilisation des arbres : Représentation structurée des données au format XML ou HTML.

Le nœud racine représente le document entier, les nœuds internes — les balises et éléments, et les feuilles — les nœuds de texte et attributs. Cela aide à l'analyse et à la manipulation du contenu des documents.

4. Structure organisationnelle

Utilisation des arbres : Représentation de la hiérarchie dans les organisations et entreprises.

Le nœud racine représente le directeur général, les nœuds internes — les managers et départements, et les feuilles — les employés. Cela aide à visualiser et gérer la structure organisationnelle.

5. Jeu d'échecs

Utilisation des arbres : Représentation des coups possibles dans le jeu.

Le nœud racine représente l'état initial du jeu, les nœuds internes — les coups possibles, et les feuilles — les états finaux du jeu. Cela aide à planifier des stratégies et prendre des décisions dans les programmes d'échecs.