Quiz sur les Arbres en Informatique

Prérequis

• Maîtriser les structures et les pointeurs
• Savoir représenter visuellement les structures de données
• Implémentation des piles et des files

Objectifs

• Définir le type t_node, utiliser le type t_node*
• Définir le type t_tree
• Implémenter les algorithmes classiques d'arbres de manière récursive
• Parcours en largeur et en profondeur d'arbres

Organisation

• 1 cours (2h)
• 1 séance d'exercices (2h)
• 1 session de TP (3h)

Structures d'arbres

• Ressemblance aux listes: chaque élément pointe vers le suivant
• Arbre binaire: chaque élément pointe vers deux autres nœuds
• Représentation de haut en bas

Le type t_node

• Un nœud est semblable à une cellule de liste, mais stocke deux pointeurs.
• Les pointeurs sont nommés left et right pour faciliter la visualisation.
• Définition du type t_node:

  typedef struct s_node {
    struct s_node *left;
    T value; // T est un type quelconque (int, float, etc.)
    struct s_node *right;
  } t_node;
  

Représentation d'un nœud

• Représentation standard: left value right
• Représentation compacte: value left right
• Représentation symbolique (plus facile à lire, mais pas explicite des pointeurs)

Similarités avec les cellules d'une liste

• Créer un nœud via un algorithme réutilisable (createNode())
• L'algorithme doit prendre une valeur comme paramètre.
• Retourner un pointeur vers un nœud (type t_node*).

Le type t_tree

• Une structure contenant un pointeur vers le nœud racine de l'arbre.
• La racine est le premier nœud de l'arbre.
• Définition du type t_tree:

  typedef struct s_tree {
      t_node *root;
  } t_tree;
  

Représentation des arbres non vides

• Certains nœuds ont des enfants (left et right).
• Certains nœuds n'ont qu'un seul enfant (left ou right).
• Certains nœuds n'ont pas d'enfant (left et right sont NULL). Ces nœuds sont appelés feuilles.

Définitions standards

• La profondeur d'un nœud est la distance à la racine.
• La hauteur d'un arbre est la profondeur maximale de ses nœuds.

Récursivité et arbres

• La récursivité est un moyen naturel d'effectuer des opérations sur les arbres.
• Cette méthode est simple et efficace pour les opérations sur les arbres.

Définition récursive d'un arbre - sous-arbres

• La variable mytree est de type t_tree.
• mytree.root et temp sont tous deux de type t_node*.
• Cela permet la récursivité (comme pour les listes).
• Ecrire une fonction récursive pour le type t_node*.
• Pour mytree, le premier appel récursif sera avec mytree.root.

Un exemple : la fonction height()

• Calculer la hauteur d'un arbre.
• Si l'arbre est vide, sa hauteur est -1.
• Sinon, la hauteur est 1 + le maximum entre les hauteurs des sous-arbres gauche et droit.

Exemples

• La hauteur de mytree est la hauteur de son champ root.
• Si mytree.root est NULL, la hauteur est -1.
• Calculer la hauteur d'un noeud (t_node*).

Algorithme récursif height()

• Étape 1: Calculer la hauteur d'un nœud (t_node*).
• Si le pointeur est NULL, la hauteur est -1.
• Sinon, c'est 1 + le maximum entre la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit.
• Retourner cette hauteur.
• Écrire l'algorithme nodeHeight().
• Que doit retourner cet algorithme ? Une valeur entière.
• t_node* est-il modifié lors du calcul de sa hauteur ? Non.

Algorithme récursif Height() (entête)

• Algorithme nodeHeight(p_node: t_node*): entier.

La suite

• Si p_node est NULL, la hauteur est -1.
• Sinon, la hauteur est 1 + le maximum des hauteurs des sous-arbres gauche et droit.

Compter le nombre de nœuds dans un arbre binaire

• Algorithme récursif nodeCount() à voir en TD/TP.

Créer un arbre binaire aléatoire

• L'algorithme EmptyTree() initialise un arbre vide.
• Créer un nouveau nœud et choisir un emplacement aléatoire pour l'insérer dans l'arbre.

L'algorithme addRandomNode()

• Prend une valeur de type char et un arbre (t_tree*) en paramètres.
• Modifie l'arbre si nécessaire (met à jour root si l'arbre est vide).

Visualisation

• Décrire l'algorithme addRandomNode().
  • Créer un nouveau nœud.
  • Trouver un emplacement dans l'arbre.
  • Insérer le nouveau nœud à l'emplacement trouvé.

Parcourir un arbre

• Plusieurs modes de parcours d'arbres existent.
• Pour les listes, un seul parcours est possible (en avant).
• Pour les arbres, la récursivité est souvent utilisée.

Schéma général de récursivité

• Algorithme récursif processNode() pour effectuer une opération sur les nœuds.
• Appel récursif pour les enfants gauche et droit.

Parcours en profondeur

• La récursivité précédente décrit un parcours en profondeur.
• Il existe 3 types importants: préfixe, infixe, postfixe.

Illustration

• Exemple d'arbre binaire (mytree).

Parcours préfixe

• Algorithme prefixTraversal() : afficher la valeur du nœud courant, puis gérer les sous-arbres (left, right).

Parcours postfixe

• Algorithme postfixTraversal() : gérer les sous-arbres (left, right), puis afficher la valeur du nœud courant.

###Parcours infixe

• Algorithme infixTraversal() : gérer le sous-arbre gauche, afficher la valeur du nœud courant, puis gérer le sous-arbre droit.

Catégories d'arbres binaires

• Arbre strict/localement complet : chaque nœud a soit 0 soit 2 enfants.
• Arbre binaire complet : tous les niveaux sont remplis sauf le dernier, où les feuilles sont alignées à gauche.
• Arbre parfait : tous les niveaux sont pleins.
• Arbre dégénéré : chaque nœud a au plus un enfant (comme une liste chaînée).

Parcours en largeur

• Parcours itératif.
• Une structure de données (file) est utilisée pour stocker les nœuds à visiter au prochain niveau.

Arbres binaires de recherche (BST)

• Caractéristique : les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud courant, et les valeurs du sous-arbre droit sont supérieures.

Insertion d'une nouvelle valeur dans une BST

• Décrire comment insérer une nouvelle valeur dans un arbre binaire de recherche.
• L'insertion se fait toujours en tant que feuille.

BST vs ordre d'insertion/équilibrage d'arbre

• Plusieurs BST peuvent stocker les mêmes valeurs.
• L'ordre d'insertion affecte la structure de l'arbre.
• Des techniques d'équilibrage peuvent améliorer la performance de la recherche.

Algorithme d'insertion de la BST

• Algorithme pour insérer une nouvelle valeur dans un arbre binaire de recherche.
• Parcourir l'arbre pour trouver l'emplacement approprié.
• Insérer le nouveau noeud qui devient une nouvelle feuille.

Exemples de programmes

• Exemples de codes (Python ou C++).

Problèmes de complexité des BST

• Complexité de recherche.
• Meilleur cas (arbre équilibré), recherche efficace (complexité logarithmique).
• Pire cas (arbre dégénéré): recherche linéaire (complexité linéaire).

Testez vos connaissances sur les arbres en informatique avec ce quiz détaillé. Explorez des concepts tels que la récursivité, la hauteur des arbres et les parcours. Parfait pour les étudiants en informatique et les passionnés d'algorithmes.