\section{Arbre binaire}


\subsection{définition}

Un arbre binaire est un ensemble 
fini $X$ dont les éléments sont
des noeuds, muni d'une relation
de précédence $x \leadsto y$ vérifiant 
les propriétés:
\begin{enumerate}
\item Tous les noeuds possèdent un prédécesseur, 
sauf un noeud particulier : la racine.
\item Tous les noeuds possèdent au plus deux
successeurs. 
\end{enumerate}

Les éléments sans successeurs dont des feuilles. 
L'arbre est dit complet si tous les noeuds qui ne
sont pas des feuilles possèdent exactement deux
successeurs.

Le fameux lemme du Berger fou montre que le
nombre de noeuds $n$ et le nombre de feuilles
$f$ sont liés par la relation :

$$
          n = 2 f - 1
$$
\begin{lemme}[Berger fou] 
\label{BERGER}
Soit $f$ une application
surjective d'un ensemble fini $E$ sur un ensemble
$F$ telle que tous les éléments de $F$ ont exactement
$\mu$ antécédants, alors
$$
	\sharp E     = \mu \times  \sharp F.
$$
\end{lemme}

\subsection{tableau}

On peut représenter un arbre binaire d'ordre $n$
dans un tableau de taille $n$. Comment ?


\subsection{pointeur}


\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{arbre/ra.png}
\end{center}
\caption{\label{RA}Un arbre en mémoire. L'image \shell{png}
a été obtenue à partir de la fameuse commande \shell{dot} de
du projet \SE{graphviz}.} 
\end{figure}

\lstinputlisting[float, language=Bash, emph={dot}]{arbre/makefile}
\lstinputlisting[float, style=gcc]{arbre/ra.c}

\begin{exercice}
Implanter une fonction \gcc{int hauteur(arbre a)}
pour calculer la hauteur d'un arbre.
\end{exercice}
\begin{exercice}
Implanter une fonction \gcc{int feuille(arbre a)}
pour calculer le nombre de feuilles d'un arbre.
\end{exercice}


\subsection{arbre de recherche}

Un arbre de recherche est un arbre binaire dont
les sommets possèdent une clé vérifiant :
$$
	clef (G(x))  \leq clef(x) \leq clef( D(x) )
$$


\subsection{equilibre}


