language: C++ 4.7.2 (gcc-4.7.2)
date: 919 days 15 hours ago
link:
visibility: public 
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

/**
 * \file BST.h
 * \brief Classe d�finissant un arbre du laboratoire#8
 * \author Abder
 * \version 0.1
 * \date mai 2009
 *
 * Definition de la classe Arbre et de ses m�thodes de parcours 
 *
 */
 
#ifndef _BST
#define _BST
 
#pragma warning( disable : 4290 )
#include <stdexcept>
#include <iostream>
#include <vector>
#include <queue>
 
namespace Arbre_Lab8
{
 
        /** 
        * \class Graphe
        *
        * \brief classe g�n�rique repr�sentant un arbre
        *
        *  La classe g�re un arbre g�n�rique. L'impl�mentation
        *  se fait par cha�nage.
        */ 
        template <typename E>
        class Arbre
        {
        public:
                /**
                 *  \brief Constructeur #1 par d�faut
                 *
                 * \post Une instance de la classe Arbre est initialis�e
                 * 
                 */
                Arbre(){racine = 0;}
 
                /**
                 *  \brief Constructeur#2 � partir des tableaux de visite sym�trique et au p�re
                 *
                 * \pre Il faut qu'il y ait suffisamment de m�moire
                 *
                 *  \post l'arbre dont les visites sym�trique et au p�re sont contenus 
                 *                respectivement dans les tableaux tabS et *ptr est construit 
                 *
                 *  \exception bad_alloc s'il n'y a pas assez de m�moire
                 */
                Arbre(E *tabS, int debut, int fin, E **ptr, int & card) throw(std::bad_alloc);
 
                /**
                 *  \brief Constructeur de copie
                 *
                 * \pre Il faut qu'il y ait suffisamment de m�moire
                 *
                 *  \post une copie profonde de l'arbre source est instanci�e
                 *
                 *  \exception bad_alloc s'il n'y a pas assez de m�moire
                 */
                Arbre(const Arbre& source) throw(std::bad_alloc) {_auxCopier(source.racine,racine);}
 
                /**
                 *  \brief Destructeur
                 *
                 *  \post l'instance de Graphe est d�truite
                 */
                ~Arbre() {_auxDetruire(racine);}
 
                
                /**                       
                 *  \brief Lister un arbre
                 *
                 * Le listage  se fait en aprcourant l'arbre en ordre (parcours sym�trique)
                 *
                 * \pre Il y a assez de m�moire
                 *
                 * \post L'arbre est inchang�
                 *
                 * \exception bad_alloc s'il n'y a pas assez de m�moire
                 * 
                 */
                void lister(std::vector<E>&) const throw(std::bad_alloc); 
 
                
                /**                       
                 *  \brief Parcourir en Pr�-Ordre un arbre (priorit� au p�re) 
                 *
                 * \post L'arbre est inchang�
                 * 
                 */
                void parcourirPreOrdre(void (* traitement)(E &iteme)) const;
 
                /**                       
                 *  \brief Parcourir un arbre par niveau 
                 *
                 * \post L'arbre est inchang�
                 * 
                 */
                void parcourirParNiveau(void (* traitement)(E &iteme)) const;
 
 
                private:
                /** 
                * \class Noeud
                *
                * \brief classe interne repr�sentant un noeud typique de l'arbre
                *
                *  La classe repr�sente un noeud typique
                *  pour impl�menter un arbre par cha�nage.
                */
                class Noeud
                {
                  public:
                        E data;                 /*!< La donn�e dans l'arbre*/
                        Noeud *gauche;  /*!< Pointeur vers le fils gauche*/
                        Noeud *droite;  /*!< Pointeur vers le fils droit*/
                        /**                       
                         * \brief Constructeur de la classe Noeud
                         *
                         * \post un noeud typique est intialis�
                         * 
                         */
                        Noeud( const E&d ): gauche( 0 ), data( d ), droite( 0 ) { }
                };
 
                // Les membres donn�es
                Noeud * racine; /*!< La racine de l'arbre*/
                
                // Les membres fonctions priv�s
                
                // Les auxiliaires r�cursifs
                // pour l'insertion et les diff�rents parcours,
                
 
                /**                       
                 *  \brief Parcourir en En-Ordre un sous-arbre
                 *
                 * Fonction r�cursive auxiliaire pour la m�thode lister().
                 *
                 * \post Le sous-arbre est inchang�
                 * 
                 */
                //void _auxEnOrdre(Noeud*, std::vector<E>&) const;
 
                /**                       
                 *  \brief Copier deux sous-arbre
                 *
                 * Fonction r�cursive auxiliaire pour le constructeur de copie
                 *
                 * \post Le sous-arbre source est inchang�
                 * 
                 */
                void _auxCopier( Noeud *, Noeud*&) throw (std::bad_alloc);
 
                /**                       
                 *  \brief D�truire un sous-arbre
                 *
                 * Fonction r�cursive auxiliaire pour le destructeur
                 *
                 * \post Le sous-arbre est d�truit
                 * 
                 */
                void  _auxDetruire(Noeud * &t);
 
                /**                       
                 *  \brief Parcourir en Pre-Ordre un sous-arbre
                 *
                 * Fonction r�cursive auxiliaire pour le parcours en pr�-ordre
                 *
                 * \post Le sous-arbre est inchang�
                 * 
                 */
                void _auxPreOrdre(Noeud *,void (* traitement)(E&)) const;
 
                /**                       
                 *  \brief Construction d'un arbre � partir des tableaux de 2 visites (p�re et sym�trique)
                 *
                 * Fonction r�cursive auxiliaire pour le constructeur #2
                 * 
                 *  \pre Il faut qu'il y ait suffisamment de m�moire
                 *
                 *  \post Le sous-arbre construit est retourn�
                 *
                 *  \exception bad_alloc s'il n'y a pas assez de m�moire
                 */
                Noeud * _auxPereSym(E *tabS, int debut, int fin, E **ptr, int &card) throw(std::bad_alloc);
 
 
        };
}//Fin du namespace
 
#include "BST.inl"
 
#endif