CM #4 Arbres binaires PDF 2024/2025

CM #4 Arbres binaires Nicolas FLASQUE TI301 - P2 2024/2025 Prérequis: Maîtriser les structures et les pointeurs Savoir representer visuellement des structures de données Implémentation des piles et des files Objectifs : Définir le type t_node, utiliser le type t_node * Défi...

CM #4 Arbres binaires Nicolas FLASQUE TI301 - P2 2024/2025 Prérequis: Maîtriser les structures et les pointeurs Savoir representer visuellement des 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) Les structures d’arbres Assez similaire aux listes : Dans une liste, chaque élément (t_cell) pointe vers la cellule suivante. Dans un arbre binaire, chaque élément (t_node) pointe vers deux autres nœuds. Les arbres sont représentés de haut en bas : Le type t_node Un nœud dans un arbre est similaire à une cellule d’une liste, mais stocke deux pointeurs. Afin de les distinguer et de faciliter la visualisation, ces pointeurs seront nommés 'left' et 'right'. Ainsi, la définition du type t_node : typedef struct s_node { struct s_node *left ; T value ; // T est un type quelconque : int, float ou autre. struct s_node *right ; } t_node; Représentation d'un nœud La représentation standard d’un noeud serait : Nous pouvons utiliser une représentation compacte : Ou même utiliser ce genre de symbole : Plus confortable, mais pas de représentation explicite des pointeurs ! Similarités avec les cellules d’une liste La création d'un nœud se fait via un algorithme à réutiliser: createNode() ; Cet algorithme doit : 1) Prendre comme paramètre : la valeur à stocker dans le noeud ; 2) Retourner un pointeur vers un noeud (type p_node). Ainsi, son entête sera : Algorithme createNode(val :T): t_node* Rappelez-vous, T est un "certain type" : soit int, soit float, soit tout autre type... Visualisation de la creation d'un t_node – stockant des 'int' var p_nouv :t_node * p_node  createNode(12 Le type t_tree Une fois de plus, comme pour les listes, un arbre est une structure, contenant un pointeur vers le "premier" nœud de l'arbre. Selon la convention de dénomination habituelle, le "premier" nœud d'un arbre est appelé "racine" de l'arbre. Ainsi, la définition du type t_tree : Pour comparaison / analogie : typedef struct s_tree typedef struct s_std_list { { t_node *root ; t_cell *head; } t_tree ; } t_std_list; Représentation Soit la définition de la variable suivante : var mytree : t_tree mytree Alors sa représentation est : Où mytree.root est un pointeur non initialisé. Représentation des arbres non vides Supposons que le type de valeur stockée dans les noeuds est 'char'. (chaque noeud stocke une valeur 'char'). Voici un exemple de la façon dont un tel arbre est représenté Certains nœuds ont des ”enfants" left et right. Certains nœuds ont un ”enfant" left ou right, l'autre étant NULL. Certains nœuds ont à la fois les ”enfants" left et rightà NULL : ces nœuds "terminaux" sont appelés "feuilles" de l'arbre. Représentation alternative Beaucoup plus facile à lire, mais aucun pointeur n'est explicitement illustré ! Représentation utilisée dans les TPs Une fonction displayTree() sera disponibles pour vous lors des TPs à venir sur les arbres. Un arbre sera affiché comme tel : Définitions standards La ”profondeur" d'un nœud est sa "distance" au nœud racine : chaque "rangée" de l'arbre est au même profondeur. Profondeur 0 Profondeur 1 Profondeur Niveau 3 2 Niveau 4 3 Profondeur  Définitions standard La "hauteur" d'un arbre est égale à la profondeur maximale parmi tous ses nœuds. Hauteur = 5 Hauteur = 4 De : https://algo.developpez.com/faq/ ? page=Structures- arborescentes Récursivité et arbres Pour les listes : la récursivité et l'itération peuvent toutes deux être utilisées Pour les arbres : la récursivité est un moyen "naturel" d'exprimer les opérations classiques BONNE NOUVELLE BONNE NOUVELLE ? Nous devons utiliser la récursivité Vous devez maîtriser la récursivité pour pour traiter les arbres de manière traiter des arbres de manière simple et simple et efficace efficace Définition récursive d'un arbre - sous-arbres Soit mytree une variable de type t_tree. Indice : typedef struct s_tree { Question : Quel est le type de mytree.root ? t_node *root ; } t_tree ; t_node * Question : Quel est le type des pointeurs left et right d’un noeud ? Indice : typedef struct s_node { struct s_node *left ; T value ; // T est un type quelconque : int, float ou autre. struct s_node *right ; } t_node, *p_node ; struct s_node *, aka t_node * Définition récursive d'un arbre - sous-arbres Soit mytree une variable de type t_tree. Soit temp une variable de type t_node * Alors : mytree.root et temp sont tous deux de type t_node * Cela permet la récursivité, tout comme pour les listes Pour écrire une fonction récursive pour les arbres : 1) Ecrire une fonction récursive pour le type t_node * 2) Pour mytree, provoquer le premier appel récursif avec mytree.root Un exemple : la fonction height() Comment calculer la hauteur d'un arbre (à partir de root) ? Si l'arbre est vide : sa hauteur est de -1. Si l'arbre n'est pas vide, sa hauteur est : 1 + le maximum entre la hauteur de son "sous-arbre" gauche la hauteur de son "sous-arbre" droit Étape 1) calculer la hauteur d'un t_node * Étape 2) calculer la hauteur de l'arbre à partir du champ root Exemples La hauteur de mytree est la hauteur de son champ root. Ici, la hauteur est de -1, car mytree.root == NULL Exemples La hauteur de "ce qui reste à gauche" est la hauteur du champ root->left : Si c'est NULL, c'est 0. Si non : 1+max('ce qui reste à gauche', 'ce qui reste à droite') ; Exemples Si le pointeur vaut NULL : la hauteur vaut 0 Si non : 1+max('ce qui reste à gauche', 'ce qui reste à droite') ; Algorithme récursif height() 1) Étape 1 : hauteur d’un noeud t_node * Si le pointeur est NULL : sa hauteur est de -1. Sinon : c’est 1+max('ce qui reste à gauche', 'ce qui reste à droite') Écrivons l’algorithme nodeHeight() : Question : Que doit retourner cet algorithme ? Une valeur entier Question : le t_node * est-il modifié lors du calcul de sa hauteur ? Non Algorithme récursif Height() : entête D'où l’entête : algorithme nodeHeight(p_node : t_node *): entier puis l’algorithme... algorithme nodeHeight(p_node : t_node *): int var height : entier // c'est récursif, donc... retourner height  D’où l’entête La suite : algorithme nodeHeight(p_node : t_node *): int puis l’algorithme... algorithme nodeHeight(p_node : t_node *): int var height : entier // c'est récursif, donc... retourner height // Un node ’NULL’ est de hauteur -1 si (p_node = NULL) height = -1; // sinon on appellee nodeHeight() pour chaque noeud fils sinon { height  1+max(nodeHeight(p_node->left),nodeHeight(p_node->right)); } Compter le nombre de nœuds dans un arbre binaire? Au moyen d’un algorithme récursif nodeCount() À voir en TD/TP Créer un arbre binaire aléatoire Soit mytree un t_tree stockant des char. On utilisera l’algorithme EmptyTree()pour l’initialiser : Algorithme EmptyTree(): t_tree var atree : t_tree atree.root  NULL; retourner atree; Créer un arbre binaire aléatoire Objectif : créer un nouveau nœud et trouver un endroit dans l’arbre où l’insérer Cet endroit sera choisi aléatoirement : Faîtes attention au À CHAQUE ÉTAPE: cas de l’arbre vide Choisir aléatoirement entre ’left’ et ‘right’ S’il n’y a pas encore de nœud à cet endroit, Y insérer le nouveau nœud Sinon, y aller et … L’algorithme addRandomNode() Prérequis : Prend en paramètre une valeur de type char, et l’arbre dans lequel nous voudrions ajouter le noeud Est-ce que cet algorithme est susceptible de modifier l’arbre?  (est-ce que le champ'root’ peut-être modifié?) Oui! Si l’arbre est vide alors le champ 'root’ sera modifié. Donc l’entête sera : algorithme addRandomNode(p_tree : t_tree *, val : char) Visualisation algorithme addRandomNode(p_tree:t_tree *,val:char) temp @ var p_nouv : t_node * var temp : t_node * p_nouv  createNode(val) temp  p_tree->root // test si arbre vide si (p_tree->root = NULL) p-tree->root  p_nouv Si l’arbre n’est pas vide temp sera notre curseur pour parcourir l’arbre Choisir aléatoirement entre: 0 (essayer à gauche) et 1 (essayer à droite) Exemple : On tire 1 donc on essaie à droite Si l’endroit est libre (pas de nœud) on peut insérer p_nouv à droite de temp ? Quelle condition vérifie que l’endroit est libre ? Si(temp->right == NULL)alors, Si(temp->right != NULL) alors, l’emplacement est disponible l’emplacement n’est pas disponible  p_tree temp Allons à droite @ root @ @ Ici, ce n’est pas value disponible, alors, nous 't' allons à cet emplacement left right et relançons le tirage @ @ value value Se déplacer à droite 'K' 'z' signifie left right left right @ @ @ @ temp  temp->right value '8' left right @ @  p_tree temp Suite @ root @ @ Choisir aléatoirement entre: 0 (essayer à gauche) et 1 (essayer à value droite) 't' left right Exemple : On tire 1 donc essayer à @ @ droite (encore !) value value 'K' 'z' Est-ce que l’emplacement à droite left right left right de temp est libre pour insérer @ @ @ @ p_nouv ? value Oui car temp->right vaut NULL '8' left right Alors, insérer p_nouv à droite de @ @ temp.  p_tree temp @ root @ @ value Dernière 't' étape left right @ @ value value 'K' 'z' left right left right @ @ @ @ value '8' left right @ @ temp->right  p_nouv addRandomNode() La suite en TD/TP Parcourir un arbre (comparé aux listes) Il existe de nombreuses manières différentes de " visiter " ou de parcourir tous les nœuds d'un arbre. Dans une liste (std) , il n'y a pas d'autre choix que d'aller 'en avant', en utilisant le pointeur next. Dans un arbre, il y a un choix à faire entre 'gauche' et 'droite' (gauche seulement ? gauche d'abord ? droite seulement ? droite d'abord ?). Nous verrons comment organiser la récursivité pour ordonner le parcours. Les files et les piles nous seront également utiles pour un parcours itératif des arbres. Schéma général de récursivité Soit processNode() un algorithme récursif qui effectue une opération sur les noeuds : Algorithme processNode(p_n : t_node *,...):type // peut-être d'autres paramètres // bloc d’instructions (1) si (p_n->left ≠ NULL) appel récursif :... processNode(p_n->left,...) // bloc d’instructions (2) si (p_n->right ≠ NULL) appel récursif :... processNode(p_n->right,...) // bloc d’instructions (3) retourner... Parcours en profondeur La récursivité précédente applique un parcours dit "en profondeur" d'un arbre binaire. Les positions des blocs d’instructions (par rapport aux appels récursifs), indiquent 3 principaux types de parcours en profondeur: 1. Parcours dit 'préfixe' 2. Parcours dit 'infixe' 3. Parcours dit 'postfixe' Exemples à venir ! Illustration Soit mytree un arbre binaire stockant des valeurs de type char. mytree est initialisé de cette façon : Exemples de parcours pour afficher les valeurs des noeuds Parcours préfixe Algorithme prefixTraversal(pn : t_node *) afficher(pn->valeur) appel récursif pour pn->left appel récursif pour pn->right Code couleur : Fonction active entourée en vert Fonction en attente entourée en bleu Fonction terminée entourée en rouge Algorithme prefixTraversal(pn : t_node *) afficher(pn->valeur) appel récursif pour pn->left appel récursif pour pn->right Sorties : - + 3 1 / 7 x 3 2 Parcours préfixe Les anciennes calculatrices PN (Polish Notation) utilisent ce type de notation pour entrer les opérations ! Parcours postfixe Algorithme postfixTraversal(pn :t_node *) appel récursif pour pn->left appel récursif pour pn->right afficher(pn-> valeur) Trouvons ensemble les sorties : Parcours postfixe Algorithme postfixTraversal(pn :t_node *) appel récursif pour pn->left appel récursif pour pn->right afficher(pn-> valeur) Sorties : 3 1 + 7 3 2 X / - parcours infixe Algorithme infixTraversal(pn:t_node *) appel récursif pour pn->left Afficher(pn->valeur) appel récursif pour pn->right Trouvons ensemble les sorties : parcours infixe Algorithme infixTraversal(pn:t_node *) appel récursif pour pn->left Afficher(pn->valeur) appel récursif pour pn->right Trouvons ensemble les sorties : Sorties : 3 + 1 Sorties : - 3+1-7/3x2 7 / 3 x Manipulation des parenthèses 2 et des priorités : TD/TP Catégories d'arbres binaires Un arbre "strict" ou "localement complet" est un arbre où chaque nœud a soit 0 soit 2 fils. Un arbre binaire complet est un arbre dans lequel tous les niveaux sont remplis à l'exception éventuelle du dernier, dans lequel les feuilles sont alignées à gauche. Un arbre "parfait" est un arbre dont tous les niveaux sont complets. Un arbre "dégénéré" est un arbre dont chaque nœud a au plus un enfant (en fait, il s'agit d'une liste). Illustrations Strict oui Complet non Parfait non Illustrations Strict non Complet non Parfait non Illustrations Strict oui Complet oui Parfait non Illustrations Strict oui Complet oui Parfait oui Parcours en largeur Il s’agit de visiter les nœuds d'un arbre, de la racine au dernier niveau, de gauche à droite à chaque niveau de profondeur. 0 1 2 3 Sorties : -+/317x32 Parcours en largeur Difficile de faire une définition récursive d’un parcours en largeur Pour chaque niveau, stockez les enfants des nœuds pour les visiter "après". Nous avons besoin d'une structure de données appropriée pour le faire... Numérotons les nœuds pour voir si nous pouvons trouver la structure de données qui convient à nos besoins... Parcours en largeur Toujours commencer par 1 (le nœud racine) : De 1 : stocker 2 et 3 Niveau suivant De 2 : stocker 4 et 5 De 3 : stocker 6 et 7 Niveau suivant De 4 : ne rien stocker De 5 : ne rien stocker De 6 : ne rien stocker De 7 : stocker 8 et 9 Niveau suivant : De 8 : ne rien stocker De 9 : ne rien stocker Fin Comment les nœuds sont stockés ? Toujours commencer par 1 (le nœud racine) : De 1 : stocker 2 et 3 Niveau suivant De 2 : stocker 4 et 5 1 2 3 4 5 6 7 8 9 De 3 : stocker 6 et 7 Niveau suivant De 4 : ne rien stocker De 5 : ne rien stocker De 6 : ne rien stocker Ce comportement devrait vous rappeler une De 7 : stocker 8 et 9 structure de données que vous connaissez Niveau suivant : De 8 : ne rien stocker De 9 : ne rien stocker Fin C'est une file, stockant des valeurs de type t_node * Parcours en largeur Algorithme (à implémenter en TP) Attention, certains cas ne sont pas traités par cet algorithme général. Algorithme parcoursEnLargeur(t : t_tree) var q : t_queue var cur : t_node * q