\thumb

%%%%%%%%%%%%%%%%%%%%

\begin{vf}{Vérification de connaissances}{5} % titre , temps
Les affirmations suivantes sont-elles vraies ou fausses ? Justifier la réponse.

\begin{questions}
\item Le nombre maximal de n\oe uds d'un arbre binaire de hauteur $h$ est $2^{h}-1$.


\item L'arbre binaire suivant est un ABR.
\begin{figure}
\begin{center}
\includegraphics{200_arbres-exo-vf01}
\figcaption{Arbre binaire}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{200_arbres-exo-vf02}
\figcaption{Arbre binaire}
\label{200_arbres-exo-vf02}
\end{center}

\end{figure}
\item Le parcours en profondeur par ordre préfixe de l'arbre binaire de la\linebreak figure \ref{200_arbres-exo-vf02} donne :
\begin{center}
R -- A -- C -- I -- N -- E -- B -- O -- L
\end{center}

\item Le parcours en profondeur par ordre postfixe de l'arbre binaire de la figure \ref{200_arbres-exo-vf02} donne :
\begin{center}
C -- N -- E -- I -- A -- L -- O -- B -- R
\end{center}

\item Le parcours en profondeur par ordre infixe de l'arbre binaire de la figure \ref{200_arbres-exo-vf02} donne :
\begin{center}
C -- A -- N -- E -- I -- B -- O -- L -- R
\end{center}

\item Le parcours en largeur de l'arbre binaire de la figure \ref{200_arbres-exo-vf02} donne :
\begin{center}
R -- A -- B -- C -- I -- O -- N -- E -- L
\end{center}
\end{questions}
\end{vf}

\begin{corrige}
\begin{questions}

\item \textit{Faux}. Il y a en effet au maximum :
\begin{itemize}
\item 1 n\oe ud à la racine, niveau 0;
\item 2 n\oe uds au niveau suivant, niveau 1;
\item $2^2$ n\oe uds au niveau 2;
\item etc. jusqu'à $2^h$ n\oe uds au niveau $h$.
\end{itemize}

D'après la formule $1+q+q^2+\cdots+q^n = \dfrac{q^{n+1}-1}{q-1}$, avec $q=2$ et $n=h$, on obtient au maximum $2^{h+1}-1$ n\oe uds.

\item \textit{Faux}. En effet, pour qu'un arbre soit binaire de recherche, il est\linebreak nécessaire que la clé de tout n\oe ud du sous-arbre droit issu d'un n\oe ud $N_k$ soit supérieure à la clé de $N_k$. Or, \og 14 \fg{} est la clé d'un n\oe ud du sous-arbre droit issu du n\oe ud de clé \og 18 \fg{} et $14 < 18$.

\item \textit{Vrai}. Le parcours en profondeur par ordre préfixe donne les n\oe uds dans l'ordre dans lesquels on les rencontre pour la première fois :

\Par

\begin{figure}
\begin{center}
\includegraphics{209_arbres-exo-vf02b}
\figcaption{Parcours en profondeur de l'arbre}
\end{center}
\end{figure}

\Par

Ce qui donne :

\begin{center}
R -- A -- C -- I -- N -- E -- B -- O -- L.
\end{center}

\begin{aretenir}
\begin{center}
\underline{PR\'E}fixe = \underline{PRE}mière fois
\end{center}
\end{aretenir}

\item \textit{Vrai}. Quand on liste les n\oe uds dans l'ordre postfixe  dans un parcours en profondeur, on les énumère dans l'ordre dans lequel on les rencontre pour la dernière fois. Cela donne bien :\enlargethispage*{2em}
\begin{center}
C -- N -- E -- I -- A -- L -- O -- B -- R.
\end{center}

\item \textit{Faux}. Quand on liste les n\oe uds dans l'ordre infixe dans un parcours en profondeur, si le n\oe ud a un fils gauche, on le liste lors du deuxième passage sinon, lors du premier. Cela donne alors :
\begin{center}
C -- A -- N -- I -- E -- R -- B -- L -- O.
\end{center}

\item \textit{Vrai}. Dans un parcours en largeur, les n\oe uds sont listés par hauteur (par niveau) : on commence par la racine, on continue avec les n\oe uds-fils de hauteur 1, puis on continue avec ceux de hauteur 2, etc.

Cela donne bien :

\begin{center}
R -- A -- B -- C -- I -- O -- N -- E -- L.
\end{center}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Arbres de Fibonacci}{\null}{1}{5} 
On définit un \textit{arbre de Fibonacci} comme étant un arbre $A_n$ tel que les sous-arbres gauche et droit de $A_n$ sont respectivement $A_{n-1}$ et $A_{n-2}$, en admettant que $A_0$ est un arbre avec une unique racine et $A_1$ est composé d'une racine ayant un fils gauche et un fils droit.
\begin{questions}
\item Donner une représentation sagittale de l'arbre $A_3$.
\item Les arbres de Fibonacci sont-ils des AVL ? Justifier.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Pour connaître la représentation sagittale de $A_3$, il nous faut avant tout obtenir $A_2$.

\begin{figure}
\begin{center}
\includegraphics{210_arbres-exo-arbfibo}
\figcaption{Construction des premiers arbres de Fibonacci}
\end{center}
\end{figure}

\item Rappelons qu'un arbre AVL est un arbre dans lequel, pour tout n\oe ud, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1. Les arbres de Fibonacci sont donc des AVL. En effet, pour tout entier naturel $k$, $A_k$ a une hauteur égale à $k$. Donc la différence de hauteur entre $A_k$ et $A_{k+1}$ est égale à 1. Or, $A_n$ est composé de $A_{n-1}$ (fils gauche) et $A_{n-2}$ (fils droit), de hauteur $n-1$ et $n-2$, hauteurs différant donc de 1.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{\'Ecrire une fonction d'affichage}{\null}{1}{10} 
On considère un arbre implémenté comme ci-dessous :

\Par

{
\ttfamily
arbre = [ 

'A' , 

['B', ['E'] , ['F'] ],

['C' , ['G'] , ['H'] , ['I'] ],

['D'] 

]
}

\Par

Écrire une fonction \texttt{afficher(arbre,marge)}, où \texttt{marge} est un nombre\linebreak entier, qui affiche l'arbre sous une forme plus facile à lire que cette\linebreak expression:  chaque n\oe ud doit être sur une ligne, avec une marge à gauche qui reflète la position hiérarchique (la \textit{profondeur}) du n\oe ud.
\end{exo}

\begin{corrige}
Il s'agit ici de parcourir la liste \texttt{arbre} et, pour chaque élément de cette liste, d'afficher son premier élément avec une marge égale à la valeur de la variable \texttt{marge}, puis de parcourir les listes qui suivent et de procéder de même en multipliant la marge par $n$, où $n$ est la position de la liste.

On voit alors une récursivité dans le traitement des informations. 

Un programme possible est donc le suivant:

\nathanlive{progmargin}{}
\begin{listing}{}{06-ex01.py}\end{listing}

\Par

Ce programme affiche :

\hrulefill

{\ttfamily
A

\quad B

\quad\quad E

\quad\quad F

\quad C

\quad\quad G

\quad\quad H

\quad\quad I

\quad D
}

\hrulefill
%\newpage
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Arbre binaire complet}{\null}{1}{10} 
\label{exo-arbre-binaire-complet}
\index{Arbre!Binaire complet}
Un arbre binaire complet est un arbre binaire dans lequel tous les n\oe uds qui ne sont pas des feuilles ont exactement deux fils.

\Par

Dans ce cas, il peut être représenté par une liste de longueur $2^{h+1}-1$, où $h$ est sa hauteur, où les fils gauche et droit de l'élément d'indice $i$ sont stockés en indices $2i+1$ et $2i+2$. Les feuilles manquantes peuvent être représentées par des éléments vides ou des éléments \texttt{None} par exemple.

\Par\Par

\begin{figure}
\begin{center}
\includegraphics{202_arbres-exo-complet}
\figcaption{Un exemple d'arbre binaire complet}
\label{exo:ABC}
\end{center}
\end{figure}

\Par\Par

\begin{questions}
\item Quelle est, en Python, la liste représentant l'arbre de la figure \ref{exo:ABC} ?
\item Quelle est la formule permettant de calculer la hauteur d'un arbre binaire complet en fonction de la longueur de la liste des n\oe uds ?
\item \'Ecrire alors une fonction \texttt{affiche(arbre)} qui affiche l'arbre en\linebreak fonction de la liste \texttt{arbre} en utilisant un affichage similaire à la figure \ref{exo:ABC} (sans les traits).
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\enlargethispage*{\baselineskip}
\item L'arbre de la figure \ref{exo:ABC} se représente par la liste :
\Par
\begin{center}
\ttfamily
[7,3,8,9,2,1,5,10,13,15,17,12,14,None,None]
\end{center}

Il suffit de lire les n\oe uds de gauche à droite, en descendant à partir de la racine.

\item Notons $n=2^{h+1}-1$ la longueur de la liste des n\oe uds.

Dans notre exemple, $15 = 2^4-1$ (il y a 15 éléments dans la liste, et la hauteur de l'arbre est égale à 3).

Alors,
\begin{align*}
n=2^{h+1}-1 & \iff 2^{h+1} = n+1\\
& \iff h = \log_2(n+1)-1.
\end{align*}

\item Une implémentation possible est la suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{06-ex02.py}\end{listing}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Labyrinthe et arbre binaire}{\null}{2}{10} 
\index{Labyrinthe}
On considère le labyrinthe représenté ci-dessous :

\Par

\begin{figure}
\begin{center}
\includegraphics{202_arbres-exo-labyrinthe}
\figcaption{Source : wikipédia}
\label{arbre-exo-fig-labyrinthe}
\end{center}
\end{figure}

Construire un arbre binaire représentant ce labyrinthe dans lequel chaque case est représentée par un n\oe ud. On partira du n\oe ud noté $(4,0)$ et chaque n\oe ud sera noté $(i,j)$ où $i$ et $j$ représentent respectivement la ligne et la colonne de la case correspondante.



\end{exo}

\begin{corrige}
On part de la case $(4,0)$ et nous avons un unique choix : aller à la case $(4,1)$,  et ensuite, il n'y a pas d'autre choix que d'aller en $(4,2)$:

\Par

%\begin{center}\includegraphics{arbres-exo-labyrinthe-cor01}\end{center}

\begin{center}
\includegraphics{212_arbres-exo-labyrinthe-cor02}
\end{center}

\newpage

Maintenant, nous avons le choix entre aller en $(3,2)$ ou en $(4,3)$:

\Par

\begin{center}
\includegraphics{213_arbres-exo-labyrinthe-cor03}
\end{center}

\Par

On continue ainsi jusqu'à chaque feuille pour obtenir l'arbre suivant:\enlargethispage*{3em}
\Par

\begin{center}
\includegraphics{213_arbres-exo-labyrinthe-cor04}
\end{center}
\end{corrige}


\sectionnn{Construction de classes}


%%%

\begin{exo}{Arborescence d'un répertoire}{\null}{2}{20} 
Dans cet exercice, on souhaite créer une classe nous permettant d'afficher l'arborescence d'un répertoire.

On s'aide alors de la classe suivante:

\begin{listing}{}{06-ex03.txt}\end{listing}

\begin{questions}
\item Expliquez la façon dont est défini le constructeur de la classe \texttt{Node}.

\item Expliquez les deux méthodes de cette classe.

\item En faisant appel au module \texttt{os}, écrire une fonction admettant comme argument le chemin d'un répertoire, et qui retourne un arbre représentant l'architecture du répertoire informé en argument, arbre que l'on pourra afficher à l'aide de la méthode \texttt{view} de la classe \texttt{Node}. On pourra nommer cette fonction : \texttt{getDirectoryNode(path)} .
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Le constructeur de la classe \texttt{Node} permet d'initialiser une liste nommée \texttt{self.subNodes}, ainsi qu'une variable \texttt{self.value} prenant pour valeur celle de l'argument renseigné lors de l'appel à cette classe.

Les noms des variables étant explicites, on peut supposer que la liste contiendra les n\oe uds fils et que la variable \texttt{self.value} représente l'étiquette du n\oe ud.

\item La méthode \texttt{addSubNode} admet un argument : \texttt{node}.  A priori, elle ajoute à la liste \texttt{self.subNodes} la valeur de ce dernier argument. 

Cette méthode a donc pour but d'ajouter à la liste des n\oe uds déjà existante un n\oe ud supplémentaire.

\Par


Dans la définition de la méthode \texttt{view}, on commence par tester si la liste \texttt{self.subNodes} n'est pas vide, auquel cas on affiche la valeur du n\oe ud entre crochets, avec une marge dépendant de sa profondeur dans l'arbre. Dans le cas contraire, si la liste est vide, on affiche simplement la valeur du n\oe ud, sans crochet (pour signifier que c'est une feuille).

On augmente ensuite la profondeur et on passe aux éventuels enfants par récursivité : on fait appel à cette méthode en prenant cette fois-ci chaque n\oe ud  fils.

\item Voici une proposition de fonction répondant au cahier des charges:
\begin{listing}{}{06-ex04.txt}\end{listing}
\Par
Dans cette fonction, on commence par définir la racine de notre arbre : c'est le répertoire dont on veut trouver l'architecture. On prend soin ici de ne garder que le nom du répertoire et non le chemin complet, à l'aide de l'instruction \texttt{os.path.split(path)[1]}.

Le test qui suit nous sert à voir si le chemin désigne un répertoire\linebreak (\texttt{if os.path.isdir(path)}), auquel cas on ajoute à l'arbre créé un sous-n\oe ud pour chaque répertoire et fichier qu'il contient.

\Par

Ainsi, pour afficher l'arborescence d'un répertoire, on écrira par exemple:

\Par

\hrulefill

{\ttfamily

\pychevrons tree = getDirectoryNode("C:\textbackslash\textbackslash test\_directory")

\pychevrons tree.view()
\newpage
[test\_directory]\\
\hspace*{5mm} [dir\_1]   \\
\hspace*{10mm} [dir\_11]\\
\hspace*{15mm} file\_11a.txt\\
\hspace*{15mm} file\_11b.txt\\
\hspace*{10mm} [dir\_12]\\
\hspace*{15mm} [dir\_123]\\
\hspace*{20mm} fil\_123a.txt\\
\hspace*{5mm} [dir\_2]\\
$\vdots$

\hrulefill
}

\nathanlive{prog}{Téléchargez le programme complet.}%06-ex05.py
\end{questions}
\end{corrige}


%%%%
\newpage

\begin{exo}{Arbres binaires}{\null}{3}{45} 
Dans cet exercice, on souhaite construire une classe \texttt{ArbreBinaire}, initialisée à partir d'une liste.

On se basera sur l'arbre suivant:

\Par

\begin{figure}
\begin{center}
\includegraphics{204_01-crs-ABR}
\figcaption{Arbre binaire servant d'exemple}
\label{arbre-a-implementer}
\end{center}
\end{figure}

\Par

On souhaite que cet arbre soit implémenté par la liste suivante :

{
\ttfamily
L = \newline
[ 10 , \\
\hspace*{1em} [ 7 , \\
\hspace*{2em}  [5 , [] , []] ,\\
\hspace*{2em} [9 , [8 , [] , []] , [10 , [] , []] ] \\
\hspace*{1em} ] ,\\
\hspace*{1em}[ 15 ,\\
\hspace*{2em} [ ],\\
\hspace*{2em} [ 18 , [17 , [] , []] , [ ] ]\\
\hspace*{1em} ]\\
]
}

\Par

\begin{questions}
\item \'Ecrire un constructeur de cette classe ainsi qu'une méthode \texttt{arbor} de sorte à avoir l'affichage illustré sur la figure \ref{5-ex-arbres-binaires} (voir page suivante).


\item \'Ecrire une méthode \texttt{infixe} permettant de parcourir l'arbre avec un ordre infixe et de retourner la liste des n\oe uds selon cet ordre.

\item Déduire de la question précédente une méthode permettant de vérifier si l'arbre binaire est un ABR.

\item \'Ecrire une méthode \texttt{min}\_\texttt{max} retournant un couple composé du minimum et du maximum des étiquettes de l'arbre.

\item \'Ecrire une méthode \texttt{hauteur} qui retourne la hauteur de l'arbre, puis en déduire une méthode \texttt{isAVL}  qui permet de vérifier si l'arbre est un arbre AVL.
\end{questions}

\begin{figure}
\fbox{
\begin{minipage}{\linewidth}
\ttfamily

\pychevrons A = ArbreBinaire(L)\\
\pychevrons A.arbor()\\
10\\
\hspace*{1em} 7\\
\hspace*{2em} 5\\
\hspace*{3em} -\\
\hspace*{3em} -\\
\hspace*{2em} 9\\
\hspace*{3em} 8\\
\hspace*{4em} -\\
\hspace*{4em} -\\
\hspace*{3em} 10\\
\hspace*{4em} -\\
\hspace*{4em} -\\
\hspace*{1em} 15\\
\hspace*{2em} -\\
\hspace*{2em} 18\\
\hspace*{3em} 17\\
\hspace*{4em} -\\
\hspace*{4em} -\\
\hspace*{3em} -
\end{minipage}
}
\figcaption{Illustration de l'affichage souhaité}
\label{5-ex-arbres-binaires}
\end{figure}
\end{exo}

\begin{corrige}
\begin{questions}
\item Voici une proposition de script répondant au cahier des charges de cette première question:

\begin{listing}{}{06-ex06.txt} \end{listing}

\newpage

L'idée consiste ici à construire un arbre binaire basé sur une liste de la forme \texttt{[racine , filsGauche , filsDroit]}, où \texttt{filsGauche} et \texttt{filsDroit} peuvent aussi être des arbres binaires.

\item Le parcours infixe de l'arbre peut-être obtenu à l'aide de la méthode suivante (inspirée de l'algorithme du cours page \pageref{ordre-infixe}).

\begin{listing}{}{06-ex07.txt} \end{listing}


\item Cette question pourrait être perçue comme très compliquée si nous ne remarquons pas que le parcours infixe d'un ABR donne toujours une liste croissante de nombres. On s'aide alors de la méthode \texttt{infixe} implémentée à la question précédente, ce qui donne:

\begin{listing}{}{06-ex08.txt} \end{listing}


\item 
\begin{methode}
Pour déterminer le minimum et le maximum d'un arbre (dans le cas où les étiquettes sont des nombres), il suffit de se baser sur la liste donnée par son parcours infixe : le minimum est le premier élément et le maximum, son dernier.
\end{methode}

Cela donne la méthode suivante:


\begin{listing}{}{06-ex09.txt} \end{listing}

\newpage

\item Pour calculer la hauteur d'un arbre, on ajoute 1 à la hauteur maximale des sous-arbres, ce qui donne:

\begin{listing}{}{06-ex10.txt} \end{listing}

\Par

Pour vérifier si l'arbre est bien un AVL, il faut s'assurer que pour tout n\oe ud, les hauteurs des sous-arbres diffèrent d'au plus 1. On va donc s'aider de la méthode \texttt{hauteur}:

\begin{listing}{}{06-ex11.txt} \end{listing}

\Par

On s'assure ici que l'arbre donné dans l'énoncé n'est pas un AVL.
\end{questions}

\nathanlive{prog}{Téléchargez la classe complète.}% 06-ex12.py
\end{corrige}



\begin{exo}{Une classe \og Arbre \fg{} complète}{\null}{3}{45} 
\label{exo-arbre}
Dans cet exercice, on se propose de construire une classe \texttt{Arbre} relativement complète en se basant sur ce qui a été vu en cours, notamment les algorithmes. Cette classe admet le constructeur suivant:
\begin{listing}{}{06-ex13.txt}\end{listing}

Nous souhaitons implémenter un arbre comme page ci-contre.
\enlargethispage*{\baselineskip}

\begin{questions}
\item Implémenter une méthode \texttt{Prefixe} qui retourne une liste donnant tous les n\oe uds de l'arbre dans un ordre préfixe, à l'aide d'un parcours en profondeur.

\item Implémenter une méthode \texttt{Postfixe} qui retourne une liste donnant tous les n\oe uds de l'arbre dans un ordre postfixe, à l'aide d'un parcours en profondeur.

\item Implémenter une méthode \texttt{Largeur} qui retourne une liste donnant tous les n\oe uds de l'arbre en ayant parcouru ce dernier en largeur.
\end{questions}

\begin{listing}{}{06-ex14.txt}\end{listing}

\begin{questions}
\setcounter{enumii}{3}
\item Implémenter alors une méthode \texttt{AfficheListe(chaine)} de sorte à avoir :

\hrulefill

{\ttfamily
\pychevrons tree.AfficheListe('prefixe')

['A', 'B', 'C', 'D', 'Z', 'E', 'X', 'Y', 'P', 'F', 'G',\\
'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']

\pychevrons tree.AfficheListe('postfixe')

['Z', 'D', 'X', 'Y', 'P', 'E', 'C', 'G', 'H', 'F', 'B',\\
'K','L', 'J', 'N', 'O', 'M', 'I', 'A']

\pychevrons tree.AfficheListe('largeur')

['A', 'B', 'I', 'C', 'F', 'J', 'M', 'D', 'E', 'G', 'H',\\
'K','L', 'N', 'O', 'Z', 'X', 'Y', 'P']
}

\hrulefill

\item Implémenter une méthode \texttt{Affiche} qui permet d'afficher l'arbre avec une marge, comme dans le paragraphe \ref{classe-arbre} page \pageref{classe-arbre}.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Voici une méthode \texttt{Prefixe} basée sur l'algorithme de la page \pageref{algo-ordre-prefixe} :

\begin{listing}{}{06-ex15.txt}\end{listing}

\newpage

\item Voici une méthode \texttt{Postfixe} basée sur l'algorithme de la page \pageref{algo-ordre-postfixe} :

\begin{listing}{}{06-ex16.txt}\end{listing}

\item Voici une méthode \texttt{Largeur} basée sur l'algorithme de la page \pageref{algo-largeur} :

\begin{listing}{}{06-ex17.txt}\end{listing}

\item Une méthode d'affichage sous forme de liste est alors la suivante :

\begin{listing}{}{06-ex18.txt}\end{listing}
\item En s'inspirant du script permettant l'affichage vu en page \pageref{classe-arbre} du cours, on obtient la méthode suivante:

\begin{listing}{}{06-ex19.txt}\end{listing}

\Par

\nathanlive{prog}{Téléchargez la classe complète.}% 06-ex20.py
\end{questions}
\end{corrige}



%%%%%%%%%%%%%%%

\begin{exo}{Une classe pour ABR}{\null}{3}{60} 
Dans cet exercice, on se propose de construire une classe pour représenter des arbres binaires de recherche.

On part alors du constructeur suivant:

\begin{listing}{}{06-ex21.txt}\end{listing}

où :
\begin{itemize}
\item \texttt{data} représente la valeur d'un n\oe ud;
\item \texttt{left} et \texttt{right} désignent respectivement les fils gauche et droit;
\item \texttt{parent} est le parent du n\oe ud.
\end{itemize}

Ainsi, par défaut, un n\oe ud n'a ni fils ni parent.

\Par

On initialiser un ABR en écrivant :

\Par

\texttt{A = ABR(150)}

\Par

où \og 150 \fg{}  est la valeur de la racine de l'arbre.

Pour tester les méthodes que nous allons implémenter, nous représenterons l'arbre suivant:

\Par

\begin{figure}
\begin{center}
\includegraphics{207_5-exo-ABR}
\figcaption{ABR à implémenter}
\label{ABR-a-implementer}
\end{center}
\end{figure}

\begin{questions}
\item \'Ecrire une méthode \texttt{insert} qui permet d'insérer une valeur dans l'ABR. 

\vfil\hfil\textit{Suite des questions page suivante.}

\newpage

\item \'Ecrire une méthode \texttt{affiche} permettant d'afficher l'arbre horizontalement, c'est-à-dire que l'arbre de la figure \ref{ABR-a-implementer} s'affichera sous la forme:

\Par

{\ttfamily
\def\space{8mm}
\hspace*{2\space}250\\
\hspace*{\space}200\\
%\hspace*{3\space}180\\
\hspace*{2\space}175\\
150\\
\hspace*{2\space}100\\
\hspace*{\space}45\\
\hspace*{4\space}21\\
\hspace*{3\space}18\\
\hspace*{4\space}17\\
\hspace*{2\space}12\\
\hspace*{4\space}10\\
\hspace*{3\space}7\\
\hspace*{4\space}3
}

\item \'Ecrire une méthode \texttt{hauteur} qui renvoie la hauteur de l'arbre.

\item \'Ecrire une méthode \texttt{trouve(data)} qui retourne le n\oe ud qui contient la valeur \texttt{data}, et qui retourne \og \texttt{None} \fg{} si la valeur n'est pas trouvée dans l'ABR.

\item \'Ecrire une méthode \texttt{liste} qui renvoie une liste ordonnée des valeurs contenues dans l'arbre.

\item \'Ecrire deux méthodes \texttt{is}\_\texttt{left}\_\texttt{child} et \texttt{is}\_\texttt{right}\_\texttt{child} qui vérifient si un n\oe ud est le fils gauche ou droit de son parent, ou pas. Ces méthodes doivent renvoyer un booléen.

\item \'Ecrire une méthode \texttt{minimum} qui retourne le n\oe ud ayant la plus petite valeur.

\item Le successeur d'un n\oe ud $N$ est le n\oe ud ayant la plus petite valeur supérieure à $N$.

\'Ecrire une méthode \texttt{successeur(self)} qui retourne le successeur d'un n\oe ud.

\item \'Ecrire enfin une méthode \texttt{delete} qui permet de supprimer le n\oe ud dont la valeur est un nombre passé en argument.

On pourra s'aider des méthodes \texttt{trouve} et \texttt{successeur}.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Quand on insère une valeur dans un ABR, il faut voir si celle-ci est inférieure ou égale à sa racine, auquel cas la valeur sera placée dans le sous-arbre gauche, ou au contraire supérieure, auquel cas elle sera placée dans le sous-arbre droit.

Si la valeur est inférieure ou égale à la valeur de la racine, on regarde s'il existe un fils gauche : si tel n'est pas le cas, on définit le fils gauche par la valeur à insérer, et on définit le parent comme étant la racine. Si, au contraire, le fils gauche existe, alors on répète l'opération en prenant pour racine le fils gauche : on fait donc appel à la récursivité.

Pour une valeur strictement supérieure à la valeur de la racine, on utilise un raisonnement analogue. On a alors la méthode écrite page suivante.


\begin{listing}{}{06-ex22.txt}\end{listing}

\item Le n\oe ud le plus à droite de l'arbre sera affiché sur la première ligne avec une marge dépendant de sa hauteur. À la ligne suivante devra s'afficher le parent du n\oe ud précédemment affiché, et ensuite, le fils droit du parent.

Cette façon de raisonner nous pousse à utiliser la récursivité; en effet, tant qu'il y a un fils droit, on fait appel à la méthode \texttt{affiche} en augmentant la hauteur de 1; quand il n'y en a plus, on affiche le n\oe ud et on passe au fils gauche. D'où la méthode suivante:
\begin{listing}{}{06-ex23.txt}\end{listing}

\item Pour calculer la hauteur d'un arbre, on ajoute 1 à la plus grande des hauteurs entre celles des sous-arbres gauche et droit, d'où la méthode récursive suivante :

\begin{listing}{}{06-ex24.txt}\end{listing}

\Par

\item ~\par 
\vspace*{-8mm}\begin{listing}{}{06-ex25.txt}\end{listing}

\Par\enlargethispage*{\baselineskip}

Il n'y a rien de compliqué pour cette méthode : si \texttt{data} coïncide avec la valeur du n\oe ud courant, on retourne le n\oe ud; si elle est inférieure, on va chercher du côté gauche et dans le cas contraire, du côté droit. Si rien n'est trouvé au final, on retourne \texttt{None}.




\item Là encore, rien de bien compliqué : on initialise une liste vide en argument de la méthode, on y ajoute la valeur du n\oe ud courant et si ce n\oe ud a des fils, on fait appel à cette méthode en passant la liste en argument pour chacun des fils, ce qui donne:

\begin{listing}{}{06-ex26.txt}\end{listing}


\item Une possibilité est celle donnée page suivante.

\Par

L'idée consiste ici à comparer le parent du n\oe ud courant et le fils gauche (ou droit) du parent.

\og \texttt{self is self.parent.left} \fg{} est déjà un booléen : il représente si le n\oe ud courant est bien le fils gauche de son parent. 

Ainsi, \og \texttt{ self.parent and self is self.parent.left} \fg{} s'assure que le parent existe ET que le n\oe ud courant est son fils gauche. 

Il en est bien sûr de même pour le fils droit.

\newpage

\begin{listing}{}{06-ex27.txt}\end{listing}


\item Comme nous sommes dans un ABR, le n\oe ud ayant la plus petite valeur est celui qui est situé le plus à gauche, d'où la solution suivante :
\begin{listing}{}{06-ex28.txt}\end{listing}

\Par

On parcourt l'arbre tant qu'un fils gauche existe, et si tel n'est pas le cas, c'est que l'on est sur le n\oe ud qui a la plus petite valeur.

\item Tous les n\oe uds du sous-arbre gauche de $N$ ont une valeur plus petite, donc son successeur se trouve dans son sous-arbre droit. D'après les propriétés de l'ABR, ça sera la plus petite valeur de ce sous-arbre droit : son dernier fils gauche s'il y a des descendants à gauche, sinon son premier n\oe ud.

Si le n\oe ud n'a pas de sous-arbre droit, il faut remonter dans l'arbre pour trouver une valeur plus grande car c'est le seul endroit où on pourra en trouver une. Le successeur sera le premier des parents tel que $N$ apparaît dans son sous-arbre gauche. Cela donne alors la méthode suivante :

\begin{listing}{}{06-ex29.txt}\end{listing}

\item C'est sans doute la méthode la plus difficile à écrire; il faut donc s'armer de patience et de persévérance pour arriver à nos fins.

On commence par rechercher la valeur dans l'arbre avec la méthode \texttt{trouve} car si la valeur n'existe pas, inutile de faire quoi que ce soit.

Ensuite, en définissant la méthode par : \texttt{def delete(self,data)}, on teste la valeur du n\oe ud : \texttt{if self.data == data}. 

Le cas le plus simple est quand le n\oe ud n'a pas de fils : dans ce cas, on le supprime tout simplement en spécifiant que le parent n'a plus de fils gauche ou droit selon sa position.

Si le n\oe ud a un fils unique, alors il est remplacé par son fils.

Si le n\oe ud a deux fils, on remplace le n\oe ud par son successeur :
\begin{itemize}
\item son successeur sera forcément dans son sous-arbre droit car le n\oe ud a deux enfants, donc un sous-arbre droit;
\item si son successeur a des enfants, ils ne pourront être qu'à sa droite car son successeur est dans notre cas la plus petite valeur du sous-arbre droit;
\item on remplace donc la valeur du n\oe ud courant par celle de son successeur;
\item on corrige les branches de l'arbre pour aller de notre n\oe ud vers le fils de son successeur (et vice-versa) pour rendre le successeur orphelin et le sortir de l'arbre;
\item on supprime son successeur.
\end{itemize}

Si la valeur \texttt{data} est inférieure à celle du n\oe ud courant, on s'oriente vers le sous-arbre gauche et si elle lui est supérieure, vers le sous-arbre droit. Cela donne la méthode suivante \texttt{delete} dans la classe à télécharger:
\begin{listing}{}{06-ex30.txt}\end{listing}
\Par

\nathanlive{prog}{Téléchargez la classe complète}%06-ex31.py
\end{questions}
\end{corrige}


\thumb
\AfficheCorrige
