arbres.tex 3 KB
Newer Older
Loïc Barrault's avatar
Loïc Barrault committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
%!TEX root = l2_algo3.tex


\section{Arbres}
\begin{itemize}
\item Définitions 
\begin{itemize}
\item noeud, père, fils, sous-arbres gauche et droit, hauteur, profondeur, etc.
\item Primitives : accès (valeur utile et structure), création, suppression, parcours 
\end{itemize}
\item[\ra] utilisation des pointeurs de fonction pour appliquer un traitement sur l'arbre
\item Arbre binaire, arbre n-aires

\item Arbre binaire de recherche
\begin{itemize}
\item Redéfinition des primitives (certaines deviennent non récursives)
\end{itemize}
\item Tas min et max
\begin{itemize}
\item Redéfinition des primitives: insertion, suppression
\item[+] application au tri par tas
\end{itemize}
\item Arbre AVL
\begin{itemize}
\item rotations, double rotations
\item équilibrage d'arbre
\end{itemize}
\item Arbre rouge noir
	\begin{itemize}
	\item Redéfinition des primitives: insertion, suppression
	\end{itemize}
\end{itemize}


\section{Implémentation des arbres}


{ \small
\begin{langage_c}
typedef struct noeud {
	int val; // n'importe quel type de valeur utile
	struct noeud *pere, *sag, *sad;
} t_noeud;
typedef struct noeud* t_arbre;

typedef enum type_parcours { PREFIXE, INFIXE, POSTFIXE } t_type_parcours;

/* SA: sous-arbre */
/****************************************
 * primitives de modification de la structure de l'arbre
 ****************************************/
/* renvoie l'arbre dont la racine vaut val, avec les SA sag et sad */
t_arbre creer_arbre(int val, t_arbre sag, t_arbre sad, t_arbre pere); 
Loïc Barrault's avatar
Loïc Barrault committed
54
/* supprime le SA dont la racine est donn\'ee en param\^etre  */
Loïc Barrault's avatar
Loïc Barrault committed
55
56
57
58
59
int supprimer_arbre(t_arbre*);      
t_arbre ajout_gauche(t_arbre, int);
t_arbre ajout_droit(t_arbre, int);

/****************************************
Loïc Barrault's avatar
Loïc Barrault committed
60
 * primitives d'acc\`es \`a la structure de l'arbre
Loïc Barrault's avatar
Loïc Barrault committed
61
 ****************************************/
Loïc Barrault's avatar
Loïc Barrault committed
62
t_arbre pere(t_arbre); /* renvoie le p\`ere s'il existe, NULL sinon */
Loïc Barrault's avatar
Loïc Barrault committed
63
64
65
66
67
68
69
t_arbre sag(t_arbre); /* renvoie le SA gauche s'il existe, NULL sinon */
t_arbre sad(t_arbre); /* renvoie le SA droit s'il existe, NULL sinon */

/****************************************
 * primitives de verification
 ****************************************/
int arbre_vide(t_arbre);  /* renvoie vrai si arbre vide, faux sinon */
Loïc Barrault's avatar
Loïc Barrault committed
70
int est_racine(t_arbre); /*renvoie vrai si le noeud n'a pas de p\`ere */
Loïc Barrault's avatar
Loïc Barrault committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
int est_feuille(t_arbre); /*renvoie vrai si le noeud est une feuille */

/****************************************
 * primitives de modification de la valeur de la racine
 ****************************************/
int modif_racine(t_arbre, int); /* modifie la valeur de la racine du SA */
int val_racine(t_arbre, int*);      /* renvoie la valeur de la racine du SA */

/****************************************
 * primitives d'affichage
 ****************************************/
int afficher_arbre(t_arbre, t_type_parcours);
int afficher_arbre_prefixe(t_arbre, int);
int afficher_arbre_infixe(t_arbre, int );
int afficher_arbre_postfixe(t_arbre, int);

void afficher_ancetres(t_arbre a, char end);

int parcours_prefixe(t_arbre, void (*)(int*));

\end{langage_c}
}