|
lkptr
|
test_Bin_Tree.cpp
Go to the documentation of this file.
00001 // test_Bin_Tree.cpp (c) 2007 adolfo@di-mare.com 00002 00003 /** \file test_Bin_Tree.cpp 00004 \brief Prueba de caja negra de la clase \c Bin_Tree<E>. 00005 00006 \author Adolfo Di Mare <adolfo@di-mare.com> 00007 \date 2007 00008 00009 - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04 00010 */ 00011 00012 #define lkptr_NULL_POINTERS_ARE_ALONE 00013 #undef lkptr_NULL_POINTERS_ARE_ALONE 00014 #include "Bin_Tree.h" 00015 #include "Bin_Tree_Lib.h" 00016 #include "BUnit.h" 00017 00018 #include <iostream> 00019 #include <vector> 00020 #include <algorithm> // sort() && next_permutation() 00021 #include <cassert> // assert() 00022 #include <iostream> // cout 00023 00024 /// Prueba la clase \c Bin_Tree<E>. 00025 template <class E> 00026 class test_Bin_Tree : public TestCase { 00027 public: 00028 bool run(); 00029 void do_cout(); 00030 void test_copyDeep(); 00031 void test_homomorfo(); 00032 void test_make_FBHCID(); 00033 void test_make_ab_no(); 00034 void test_swap(); 00035 void test_mirror(); 00036 void test_changeChild(); 00037 void test_heightdepth(); 00038 void test_releaseChild(); 00039 void test_makeOrphan(); 00040 void test_left_right(); 00041 void test_no_swap(); 00042 void test_move_swap(); 00043 void test_multi_child(); 00044 void test_isLeft_isRight(); 00045 void test_isRoot_isLeaf(); 00046 void test_sizeStrong(); 00047 void test_AVL_tree(); 00048 }; // test_Bin_Tree 00049 00050 /// Método principal de la prueba. 00051 /// - Requiere que recién haya sido ejecutado \c setUp() 00052 template <class E> 00053 bool test_Bin_Tree<E>::run() { 00054 test_make_FBHCID(); 00055 test_make_ab_no(); 00056 test_copyDeep(); 00057 test_homomorfo(); 00058 test_swap(); 00059 test_mirror(); 00060 test_changeChild(); 00061 test_heightdepth(); 00062 test_releaseChild(); 00063 test_makeOrphan(); 00064 test_left_right(); 00065 test_no_swap(); 00066 test_move_swap(); 00067 test_multi_child(); 00068 test_isLeft_isRight(); 00069 test_isRoot_isLeaf(); 00070 test_sizeStrong(); 00071 test_AVL_tree(); 00072 return wasSuccessful(); 00073 } 00074 00075 /** Construye el árbol de letras \c (F (B (C (D))) (H (I))). 00076 - Graba en \c COUT los resultados intermedios. 00077 \code 00078 F 00079 / \ F 00080 B H B F 00081 \ \ B F H 00082 C I B C F H 00083 \ B C D F H I 00084 D 00085 \endcode 00086 */ 00087 Bin_Tree<char> make_FBHCID( std::ostream& COUT ) { 00088 Bin_Tree<char> T; 00089 orderedInsert( T, 'F' ); IPD ( COUT, T ); COUT << std::endl; 00090 orderedInsert( T, 'B' ); IPD ( COUT, T ); COUT << std::endl; 00091 orderedInsert( T, 'H' ); IPD ( COUT, T ); COUT << std::endl; 00092 orderedInsert( T, 'C' ); IPD ( COUT, T ); COUT << std::endl; 00093 orderedInsert( T, 'I' ); IPD ( COUT, T ); COUT << std::endl; 00094 orderedInsert( T, 'D' ); IPD ( COUT, T ); COUT << std::endl; 00095 return T; 00096 } 00097 00098 /** Construye el árbol de letras \c (F (B (C (D))) (H (I))). 00099 \code 00100 F 00101 / \ 00102 B H 00103 \ \ 00104 C I 00105 \ 00106 D 00107 \endcode 00108 */ 00109 Bin_Tree<char> make_FBHCID() { 00110 Bin_Tree<char> T; 00111 orderedInsert( T, 'F' ); 00112 orderedInsert( T, 'B' ); 00113 orderedInsert( T, 'H' ); 00114 orderedInsert( T, 'C' ); 00115 orderedInsert( T, 'I' ); 00116 orderedInsert( T, 'D' ); 00117 return T; 00118 } 00119 00120 /// Verifica que \c make_FBHCID() construyó el árbol correctamente. 00121 template <class E> 00122 void test_Bin_Tree<E>::test_make_FBHCID() { 00123 Bin_Tree<char> T = make_FBHCID(); 00124 assertTrue( T.size() == strlen( "FBHCID" ) ); 00125 00126 assertTrue( T.root().data() == 'F' ); 00127 assertTrue( T.root().left().data() == 'B' ); 00128 assertTrue( T.root().left().right().data() == 'C' ); 00129 assertTrue( T.root().left().right().right().data() == 'D' ); 00130 assertTrue( T.root().right().data() == 'H' ); 00131 assertTrue( T.root().right().right().data() == 'I' ); 00132 00133 std::basic_ostringstream<char> ost; // receptor de salida 00134 ost << T; 00135 assertTrue( ost.str() == "(F (B (C (D))) (H (I)))" ); 00136 assertTrue( T.ok() ); 00137 } 00138 00139 /** Construye el árbol de letras \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))). 00140 \code 00141 a 00142 / \ 00143 / \ 00144 b e 00145 / \ / \ 00146 f h i k 00147 / \ 00148 l m 00149 / \ 00150 n o 00151 \endcode 00152 */ 00153 Bin_Tree<char> make_ab_no() { 00154 Bin_Tree<char> T, T1, T2; 00155 00156 T1 = Bin_Tree<char>('b'); { 00157 T1.makeLeftChild( Bin_Tree<char>('f') ); 00158 T1.makeRightChild( Bin_Tree<char>('h') ); 00159 } 00160 00161 T2.changeRoot('k'); { 00162 T2.makeLeftChild( Bin_Tree<char>('l') ); 00163 T.changeRoot('m'); { 00164 T.makeLeftChild( Bin_Tree<char>('n') ); 00165 T.makeRightChild( Bin_Tree<char>('o') ); 00166 } 00167 T2.makeRightChild( T ); 00168 } 00169 T.erase(); 00170 T.changeRoot('a'); { 00171 T.makeLeftChild( T1 ); 00172 T.makeRightChild( Bin_Tree<char>('e') ); { 00173 T.right().makeLeftChild( Bin_Tree<char>('i') ); 00174 T.right().makeRightChild( T2 ); 00175 } 00176 } 00177 return T; 00178 } 00179 00180 /// Verifica que \c make_ab_no() construyó el árbol correctamente. 00181 /// - \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))) 00182 template <class E> 00183 void test_Bin_Tree<E>::test_make_ab_no() { 00184 std::basic_ostringstream<char> ost; // receptor de salida 00185 ost << make_ab_no(); 00186 assertTrue( ost.str() == "(a (b (f) (h)) (e (i) (k (l) (m (n) (o)))))" ); 00187 assertTrue( make_ab_no().ok() ); 00188 } 00189 00190 /// Pasa a minúscula todas las letras de \c "T". 00191 void toLower( Bin_Tree<char> T ) { 00192 if ( T.isEmpty() ) { 00193 return; 00194 } 00195 T.changeRoot( tolower( *T ) ); 00196 toLower( T.left() ); 00197 toLower( T.right() ); 00198 } 00199 00200 /// Verifica que \c Bin_Tree<E>::copyDeep() funciona correctamente. 00201 template <class E> 00202 void test_Bin_Tree<E>::test_copyDeep() { 00203 Bin_Tree<char> T, T1, T2; 00204 T.changeRoot( 'A' ); 00205 T.makeLeftChild( Bin_Tree<char>( 'B' ) ); 00206 T.makeRightChild( Bin_Tree<char>( 'C' ) ); 00207 copyDeep( T1, T ); 00208 00209 copyDeep( T2, T1 ); { 00210 assertTrue( ! T1.same( T2 ) ); 00211 assertTrue( T1 == T2 ); 00212 } 00213 T1 = T2; { 00214 assertTrue( T1.same( T2 ) ); 00215 toLower( T2 ); 00216 assertTrue( T1 == T2 ); 00217 } 00218 00219 T1 = make_FBHCID(); { 00220 assertTrue( T1 != T2 ); 00221 } 00222 00223 copyDeep( T1, T ); { 00224 assertTrue( ! T1.same( T2 ) ); 00225 assertTrue( T1 != T2 ); 00226 toLower( T1 ); 00227 assertTrue( T1 == T2 ); 00228 } 00229 } 00230 00231 /// Verifica que \c make_FBHCID() construyó el árbol correctamente. 00232 template <class E> 00233 void test_Bin_Tree<E>::test_homomorfo() { 00234 Bin_Tree<char> T1 = make_FBHCID(); 00235 Bin_Tree<char> T2 = T1, Tmp; 00236 assertTrue( homomorfo( T1 , T2 ) ); 00237 copyDeep( T2, T1 ); 00238 toLower( T1 ); 00239 assertTrue( TestCase::toString( T1 ) == "(f (b (c (d))) (h (i)))" ); 00240 assertTrue( TestCase::toString( T2 ) == "(F (B (C (D))) (H (I)))" ); 00241 T2.makeRightChild(T1); 00242 assertTrue( toString( T1 ) == "(f (b (c (d))) (h (i)))" ); 00243 assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" ); 00244 copyDeep( T1, T2 ); 00245 assertTrue( toString( T1 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" ); 00246 assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" ); 00247 assertTrue( homomorfo( T1 , T2 ) ); 00248 assertTrue( homomorfo( T2 , T1 ) ); 00249 mirror( T2.left() ); // Tmp = T2.left(); mirror( Tmp ); 00250 mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp ); 00251 assertTrue( homomorfo( T1 , T2 ) ); 00252 assertTrue( homomorfo( T2 , T1 ) ); 00253 } 00254 00255 /// Verifica que \c Bin_Tree<E>::swap() funciona correctamente. 00256 template <class E> 00257 void test_Bin_Tree<E>::test_swap() { 00258 Bin_Tree<char> T1 = make_FBHCID(); 00259 Bin_Tree<char> T2 = 'A'; 00260 assertTrue( T1.father().isEmpty() ); 00261 00262 T2.swap(T1); 00263 00264 assertTrue( T1.size() == 1 ); { 00265 std::basic_ostringstream<char> ost; // receptor de salida 00266 IPD(ost , T2); 00267 assertTrue( ost.str() == " B C D F H I" ); 00268 } 00269 assertTrue( comp( T2.left().father(), T2 ) ); 00270 assertTrue( comp( T2.right().father(), T2 ) ); 00271 assertTrue( comp( T1.left(), Bin_Tree<char>() ) ) ; 00272 assertTrue( comp( T2.left().left(), Bin_Tree<char>() ) ) ; 00273 assertTrue( comp( T2.left().right().right(), Bin_Tree<char>('D') ) ) ; 00274 assertTrue( comp( T2.right().right(), Bin_Tree<char>('I') ) ) ; 00275 T1.changeRoot( 'H' ); 00276 T1.makeRightChild( Bin_Tree<char>('I') ); 00277 assertTrue( comp( T2.right(), T1) ) ; 00278 } 00279 00280 /// Verifica que \c Bin_Tree<E>::mirror() funciona correctamente. 00281 template <class E> 00282 void test_Bin_Tree<E>::test_mirror() { 00283 Bin_Tree<char> T1 = make_FBHCID(); 00284 assertTrue( T1.count() == 6 && height(T1) == 3 ); { 00285 std::basic_ostringstream<char> ost; // receptor de salida 00286 IPD(ost , T1); 00287 assertTrue( ost.str() == " B C D F H I" ); 00288 } 00289 00290 mirror( T1 ); 00291 00292 assertTrue( T1.count() == 6 && height(T1) == 3 ); { 00293 std::basic_ostringstream<char> ost; // receptor de salida 00294 IPD(ost , T1); 00295 assertTrue( ost.str() == " I H F D C B" ); 00296 } 00297 00298 Bin_Tree<char> T2 = T1; 00299 assertTrue( comp(T1,T2) ); assertTrue( comp(T2,T1) ); 00300 00301 copyDeep(T2,T1); 00302 char ch = T1.data(); 00303 T1 = ch+1; assertTrue( ! comp(T1, T2) ); 00304 T1 = ch; assertTrue( comp(T1, T2) ); 00305 00306 copyDeep(T2,T1); 00307 ch = T1.data(); 00308 T1 = ch+1; assertTrue( ! comp(T1, T2) ); 00309 T1 = ch; assertTrue( comp(T1, T2) ); 00310 00311 mirror( T1 ); 00312 mirror( T2 ); 00313 00314 assertTrue( comp(T1, T2) ); 00315 copyDeep( T2, T1 ); 00316 assertTrue( comp(T1, T2) ); 00317 00318 assertTrue( T1.count() == 6 && height(T1) == 3 ); { 00319 std::basic_ostringstream<char> ost; // receptor de salida 00320 IPD(ost , T1); 00321 assertTrue( ost.str() == " B C D F H I" ); 00322 } 00323 00324 T2.left().changeRoot( 'X' ); 00325 assertTrue( T2.count() == 6 && height(T2) == 3 ); { 00326 std::basic_ostringstream<char> ost; // receptor de salida 00327 IPD(ost , T2); 00328 assertTrue( ost.str() == " X C D F H I" ); 00329 } 00330 00331 T2.erase(); 00332 assertTrue( !comp(T1, T2) ); 00333 } 00334 00335 /// Verifica que \c changeLeftChild() y \c changeRightChild() funcionan correctamente. 00336 template <class E> 00337 void test_Bin_Tree<E>::test_changeChild() { 00338 {{ // test::changeChild() 00339 Bin_Tree<char> T, Tcopy; 00340 T = 'A'; // agrega la raiz 'A' A 00341 T.changeLeftChild( '0' ); // ./ \. 00342 T.changeRightChild( '1' ); // 0 1 00343 copyDeep( Tcopy , T ); 00344 assertTrue( TestCase::toString(T) == "(A (0) (1))" ); 00345 mirror( T ); 00346 assertTrue( TestCase::toString(T) == "(A (1) (0))" ); 00347 mirror( T ); { 00348 std::basic_ostringstream<char> ost; 00349 ost << T; 00350 assertTrue( ost.str() == "(A (0) (1))" ); 00351 } 00352 00353 assertTrue( comp(T, Tcopy) ); 00354 }} 00355 { // Resto de las pruebas 00356 Bin_Tree<char> T2; 00357 T2 = 'A'; // inserta la raiz // 'A' 00358 T2.changeLeftChild('0'); { // / 00359 std::basic_ostringstream<char> ost; // 0 00360 IPD (ost , T2); 00361 assertTrue( ost.str() == " 0 A" ); 00362 } 00363 00364 mirror( T2 ); { 00365 std::basic_ostringstream<char> ost; 00366 IPD (ost , T2); 00367 assertTrue( ost.str() == " A 0" ); 00368 } 00369 assertTrue( T2.count() == 2 ); 00370 } 00371 } 00372 00373 /// Verifica que \c releaseLeftChild() y \c releaseRightChild() funcionan correctamente. 00374 template <class E> 00375 void test_Bin_Tree<E>::test_releaseChild() { 00376 {{ // test::releaseChild() 00377 Bin_Tree<E> Paco = E(); // Paco Lola // 00378 Bin_Tree<E> Lola = E(); // // 00379 Bin_Tree<E> Bebe; // E() E() // 00380 Lola.makeLeftChild( E() ); // \\ / // 00381 Bebe = Lola.left(); // Bebe // 00382 Bebe.makeLeftChild( E() ); // // \\ // 00383 Bebe.makeRightChild( E() ); // E() E() // 00384 Paco.makeRightChild( Bebe ); 00385 00386 Paco.releaseLeftChild(); 00387 assertTrue( 4 == Paco.size() ); // Paco no tiene hijo izquierdo 00388 Paco.releaseRightChild(); 00389 assertTrue( 1 == Paco.size() ); // Ya Paco no tiene hijo derecho 00390 assertTrue( Paco.right() == Bin_Tree<E>() ); // El hijo derecho es un árbol vacío 00391 assertTrue( Bebe != Bin_Tree<E>() ); // Bebe todavía existe 00392 assertTrue( Bebe.father() == Paco ); // Paco sigue registrado como padre de Bebe 00393 00394 assertTrue( 4 == Lola.size() ); // Lola todavía tiene a su hijo izquierdo 00395 assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola 00396 assertTrue( Lola.left().same( Bebe ) ); // Lola si tiene hijo izquierdo 00397 assertTrue( Bebe.father() != Bin_Tree<E>() ); // Bebe no está registrado como hijo de Lola 00398 00399 Lola.releaseLeftChild(); // Ahora ya Bebe no es hijo de Lola 00400 assertTrue( ! Bebe.same( Lola.left() ) ); 00401 assertTrue( 1 == Lola.size() ); // Ya Lola no tiene hijos 00402 }} 00403 } 00404 00405 /// Verifica que \c makeOrphan() funciona correctamente. 00406 template <class E> 00407 void test_Bin_Tree<E>::test_makeOrphan() { 00408 using namespace std; 00409 {{ // test::makeOrphan() 00410 Bin_Tree<E> Paco = E(); // Paco Lola // 00411 Bin_Tree<E> Lola = E(); // // 00412 Bin_Tree<E> Bebe; // E() E() // 00413 Lola.makeLeftChild( E() ); // \\ / // 00414 Bebe = Lola.left(); // Bebe // 00415 Bebe.makeLeftChild( E() ); // // \\ // 00416 Bebe.makeRightChild( E() ); // E() E() // 00417 Paco.makeRightChild( Bebe ); 00418 00419 assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola 00420 assertTrue( Bebe.same( Paco.right() ) ); // Bebe si es hijo derecho de Paco 00421 assertTrue( Bebe.father() == Paco ); // Bebe está registrado como hijo de Paco 00422 assertTrue( Bebe.father() != Lola ); // Bebe no está registrado como hijo de Lola 00423 00424 Bebe.makeOrphan(); 00425 assertTrue( Bebe.father() != Paco ); // Ya Paco no está registrado como el padre de Bebe 00426 assertTrue( Bebe.father() == Bin_Tree<E>() ); // Bebe no tiene registrado a nadie como su padre 00427 00428 assertTrue( Bebe.same( Lola.left() ) ); // Bebe sigue registrado como hijo izquierdo de Lola 00429 assertTrue( Bebe.same( Paco.right() ) ); // Bebe sigue registrado como hijo derecho de Paco 00430 assertTrue( Bebe.father() != Paco ); // Bebe ya no está registrado como hijo de Paco 00431 assertTrue( Bebe.father() != Lola ); // Bebe ya no está registrado como hijo de Lola 00432 }} 00433 } 00434 00435 /// Verifica que \c left() y \c right() funcionan correctamente. 00436 template <class E> 00437 void test_Bin_Tree<E>::test_left_right() { 00438 using namespace std; 00439 {{ // test::left_right() 00440 Bin_Tree<E> T = E(); // no hay hijo izquierdo alguno 00441 { T.left() = E(); // sí hace el cambio 00442 // pero el destructor elimina la referencia 00443 } // sin modificar el hijo izquierdo que no existe 00444 assertTrue( T.size() == 1 ); 00445 assertTrue( T.left().isEmpty() ); // "T.left()" es una nueva referencia al hijo de "T" 00446 00447 T.makeRightChild( E() ); // esta es la forma de crear un nuevo sub-árbol derecho 00448 T.right().erase(); // no elimina al hijo derecho: borra la nueva referencia "right()" 00449 assertTrue( T.size() == 2 ); 00450 assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía 00451 00452 { // Para eliminar a un hijo hay que poner el árbol nulo en su lugar 00453 T.right() = Bin_Tree<E>(); // cambia la referencia: el hijo derecho sigue ahí 00454 assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía 00455 00456 assertTrue( Bin_Tree<E>().isEmpty() ); // referencia nula: árbol vacío 00457 00458 // esta es la forma correcta de eliminar hijos 00459 T.makeRightChild( Bin_Tree<E>() ); // elimina al hijo derecho 00460 assertTrue( T.right().isEmpty() ); // ya no existe el hijo derecho 00461 } 00462 00463 if ( T.right().isEmpty() ) { 00464 if (false) { 00465 *T.right() = E(); // ERROR: Trata de cambiar un árbol vacío 00466 } 00467 T.makeRightChild( E() ); // nuevo hijo derecho 00468 } 00469 else { 00470 T.right().changeRoot( E() ); // sí cambia el valor almacenado 00471 *( T.right() ) = E(); // efecto similar al renglón anterior 00472 } 00473 T = T.right(); // caminar hacia las hojas no cambia el valor almacenado 00474 assertTrue ( ! T.father().isEmpty() ); 00475 assertTrue( T.size() == 1 ); 00476 T = T.father(); 00477 assertTrue( T.size() == 2 ); 00478 T.right().erase(); // no cambia nada 00479 assertTrue( T.size() == 2 ); 00480 00481 Bin_Tree<E> Child = T.right(); // sostiene al hijo 00482 T.right().makeOrphan(); // elimna la conexión hijo->padre 00483 assertTrue( T.right() == Child ); // no eliminó la conexión hijo->padre 00484 assertTrue( Child.father() != T ); // ni el antiguo hijo encuentra a su padre 00485 assertTrue ( ! T.isEmpty() ); 00486 assertTrue ( ! Child.isEmpty() ); 00487 assertTrue ( Child.father().isEmpty() ); // ni el antiguo hijo tiene padre 00488 }} 00489 } 00490 00491 /// Muestra que \c swap() trabaja en una referencia. 00492 template <class E> 00493 void test_Bin_Tree<E>::test_no_swap() { 00494 {{ // test::no_swap() 00495 Bin_Tree<E> T = E(); // E() // 00496 Bin_Tree<E> Right; // \ // 00497 T.makeRightChild( E() ); // E() // 00498 00499 assertTrue( T.size() == 2 ); 00500 assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho 00501 Right = T.right(); // no compila >==> T.left().swap( T.right() ); 00502 T.left().swap( Right ); 00503 assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado 00504 assertTrue( T.size() == 2 ); 00505 00506 T.makeLeftChild( T.right() ); // E() // 00507 assertTrue( T.size() == 3 ); // / \ // 00508 assertTrue( T.left().same( T.right()) ); // \ / // 00509 assertTrue( T.right().isRightChild() ); // E() // 00510 assertTrue( T.left().isLeftChild() ); // hijo compartido 00511 00512 T.makeLeftChild( T.right() ); // ahora sí cambió el árbol 00513 T.makeRightChild( Bin_Tree<E>() ); // borra al hijo derecho 00514 assertTrue( T.size() == 2 ); 00515 assertTrue( ! T.left().same( T.right()) ); 00516 assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho 00517 assertTrue( T.left().isLeftChild() ); // Ahí está el antiguo hijo derecho 00518 }} 00519 { // Autociclo a la izquierda 00520 Bin_Tree<E> T = E(); 00521 T.makeLeftChild( T ); // autociclo 00522 for ( int i=0; i<11; ++i ) { 00523 T = T.left(); 00524 assertTrue( ! T.isEmpty() ); 00525 } 00526 assertTrue( ! T.isEmpty() ); 00527 } 00528 { // Autociclo a la derecha 00529 Bin_Tree<E> T = E(); 00530 T.makeRightChild( T ); // autociclo 00531 for ( int i=0; i<22; ++i ) { 00532 T = T.right(); 00533 assertTrue( ! T.isEmpty() ); 00534 } 00535 assertTrue( ! T.isEmpty() ); 00536 } 00537 { // Autociclo a la derecha // E() // 00538 Bin_Tree<E> T = E(); // \ // 00539 T.makeRightChild( E() ); // E() // 00540 T.right().makeRightChild( E() ); // \ // 00541 // E() // 00542 assertTrue( T.size() == 3 ); 00543 T.right().right().makeRightChild( T ); // E() <---+ // 00544 for ( int i=0; i<33; ++i ) { // \ | // 00545 T = T.right(); // E() | // 00546 assertTrue( ! T.isEmpty() ); // \ | // 00547 } // E() | // 00548 assertTrue( ! T.isEmpty() ); // \-+ 00549 } 00550 if ( false) { 00551 // Muestra cómo funcionaría el árbol un sub-arbol 00552 // pudiera ser hijo sólo de un único árbol 00553 Bin_Tree<E> T = E(); // E() // 00554 Bin_Tree<E> Right; // \ // 00555 T.makeRightChild( E() ); // E() // 00556 00557 T.makeLeftChild( T.right() ); // E() // 00558 assertTrue( T.size() == 2 ); // / // 00559 assertTrue( ! T.left().same( T.right()) ); // E() // 00560 assertTrue( T.left().isLeftChild() ); 00561 assertTrue( ! T.right().isRightChild() ); 00562 00563 T.makeRightChild( T.left() ); // E() // 00564 assertTrue( T.size() == 2 ); // \ // 00565 assertTrue( ! T.right().same( T.left()) ); // E() // 00566 assertTrue( T.right().isRightChild() ); 00567 assertTrue( ! T.left().isLeftChild() ); 00568 00569 assertTrue( T.size() == 2 ); 00570 assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho 00571 Right = T.right(); // no compila ==> T.left().swap( T.right() ); 00572 T.left().swap( Right ); 00573 assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado 00574 assertTrue( T.size() == 2 ); 00575 } 00576 } 00577 00578 /// Verifica que \c move() y \c swap() funcionan correctamente. 00579 template <class E> 00580 void test_Bin_Tree<E>::test_multi_child() { 00581 {{ // test::multi_child() 00582 // Muestra que un mismo árbol "Bebe" puede ser sub-árbol 00583 // de varios árboles 00584 Bin_Tree<E> Paco = E(); // Paco Lola // 00585 Bin_Tree<E> Lola = E(); // // 00586 Bin_Tree<E> Bebe; // E() E() // 00587 Lola.makeLeftChild( E() ); // \\ / // 00588 Bebe = Lola.left(); // Bebe // 00589 Bebe.makeLeftChild( E() ); // // \\ // 00590 Bebe.makeRightChild( E() ); // E() E() // 00591 Paco.makeRightChild( Bebe ); 00592 00593 // Como se muestra en el diagrama X, debido a este último cambio 00594 // el padre registrado de Bebe ahora es Paco 00595 00596 assertTrue( 3 == Bebe.size() ); 00597 assertTrue( 4 == Paco.size() ); // 3 de Bebe + Paco 00598 assertTrue( 4 == Lola.size() ); // 3 de Bebe + Lola 00599 00600 assertTrue( Paco.right().same( Bebe ) ); // Bebe es hijo de Paco 00601 assertTrue( Lola.left() .same( Bebe ) ); // Bebe es hijo de Lola 00602 00603 assertTrue( Bebe.father().same( Paco ) ); // El papá de Bebe es Paco 00604 assertTrue( ! Bebe.father().same( Lola ) ); // Lola no es ancestro de Bebe 00605 // corrección: "Lola" no aparece registrada como padre para "Bebe" 00606 00607 Bebe.erase(); 00608 assertTrue( Bebe.isEmpty() ); // La referencia Bebe está vacía 00609 00610 Bebe = Lola.left(); // Se llega al hijo compartido desde Lola 00611 assertTrue( ! Bebe.isEmpty() ); 00612 assertTrue( Bebe.father().same( Paco ) ); // Repito: el papá de Bebe es Paco 00613 assertTrue( ! Bebe.father().same( Lola ) ); // Repito: Lola no es ancestro de Bebe 00614 00615 if ( false ) { // Tortón !!! 00616 Bebe.left().makeRightChild( Paco ); // ciclo infinito en el árbol 00617 Bebe.right().makeLeftChild( Lola ); 00618 } 00619 }} 00620 } 00621 00622 /// Verifica que \c move() y \c swap() funcionan correctamente. 00623 template <class E> 00624 void test_Bin_Tree<E>::test_move_swap() { 00625 {{ // test::move_swap() 00626 Bin_Tree<E> Paco = E(), Lola = E(); // E() // 00627 Paco.makeLeftChild( E() ); // / \ // 00628 Paco.makeRightChild( E() ); // E() E() // 00629 00630 assertTrue( Paco.size() == 3 ); 00631 assertTrue( Lola.size() == 1 ); 00632 Paco.swap( Lola ); 00633 assertTrue( Paco.size() == 1 ); 00634 assertTrue( Lola.size() == 3 ); 00635 00636 Lola.move( Paco ); 00637 assertTrue( Paco.size() == 0 ); 00638 assertTrue( Lola.size() == 1 ); 00639 }} 00640 } 00641 00642 /// Verifica que \c isLeftChild() y \c isRightChild() funcionan correctamente. 00643 template <class E> 00644 void test_Bin_Tree<E>::test_isLeft_isRight() { 00645 {{ // test::isLeft_isRight() 00646 Bin_Tree<E> T = E(); // E() // 00647 T.makeLeftChild( E() ); // / \ // 00648 T.makeRightChild( E() ); // E() E() // 00649 00650 assertTrue( ! T.isLeftChild() ); 00651 assertTrue( T.left().isLeftChild() ); 00652 assertTrue( T.right().isRightChild() ); 00653 assertTrue( !T.left().left().isLeftChild() ); // árbol vacío 00654 assertTrue( !T.right().right().isRightChild() ); // árbol vacío 00655 }} 00656 } 00657 00658 /// Verifica que \c isRoot() y \c isLeaf() funcionan correctamente. 00659 template <class E> 00660 void test_Bin_Tree<E>::test_isRoot_isLeaf() { 00661 {{ // test::isRoot_isLeaf() 00662 Bin_Tree<E> T = E(); // E() // 00663 T.makeLeftChild( E() ); // / \ // 00664 T.makeRightChild( E() ); // E() E() // 00665 00666 assertTrue( T.isRoot() && ! T.isLeaf() ); 00667 assertTrue( T.left().isLeaf() ); 00668 assertTrue( T.right().isLeaf() ); 00669 assertTrue( !T.left().left().isLeaf() ); // árbol vacío 00670 assertTrue( !T.right().right().isRoot() ); // árbol vacío 00671 }} 00672 } 00673 00674 /// Verifica que \c sizeStrong() funciona correctamente. 00675 template <class E> 00676 void test_Bin_Tree<E>::test_sizeStrong() { 00677 using namespace std; 00678 {{ // test::sizeStrong() 00679 Bin_Tree<E> Paco = E(); // Paco Lola // 00680 Bin_Tree<E> Lola = E(); // // 00681 Bin_Tree<E> Bebe; // E() E() // 00682 Lola.makeLeftChild( E() ); // \\ / // 00683 Bebe = Lola.left(); // Bebe // 00684 Bebe.makeLeftChild( E() ); // // \\ // 00685 Bebe.makeRightChild( E() ); // E() E() // 00686 Paco.makeRightChild( Bebe ); 00687 00688 assertTrue( 4 == Paco.size() ); // Paco Lola // 00689 assertTrue( 4 == Lola.size() ); // // 00690 assertTrue( 3 == Bebe.size() ); // E() E() // 00691 Paco.right().left().makeLeftChild( Paco ); // / \\ / \ // 00692 Lola.left().right().makeRightChild( Lola ); // | Bebe | // 00693 assertTrue( Paco == Bebe.left().left() ); // \ // \\ / // 00694 assertTrue( Lola == Bebe.right().right() ); // E() E() // 00695 00696 std::set< E* > S; // hay que vaciarlo antes de incocar "sizeStrong()" 00697 S.clear(); assertTrue( 5 == sizeStrong( Paco, S ) ); 00698 S.clear(); assertTrue( 5 == sizeStrong( Lola, S ) ); 00699 00700 // Como "S" no está vacío, "sizeStrong()" usa el valor actual 00701 const int ZERO = 0; 00702 assertTrue( ZERO == sizeStrong( Bebe, S ) ); 00703 }} 00704 } 00705 00706 /// Verifica que la inserción y/o borrado AVL funciona correctamente. 00707 template <class E> 00708 void test_Bin_Tree<E>::test_AVL_tree() { 00709 if (true) { // A52512 00710 Bin_Tree<int> T; std::string watch; 00711 insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() ); 00712 insertAVL( T, 8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() ); 00713 insertAVL( T, 4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() ); 00714 insertAVL( T, 2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() ); 00715 insertAVL( T, 1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); 00716 insertAVL( T, 3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); 00717 watch = TestCase::toString( T ); 00718 00719 // se prueba que no existe inserción de un elemento ya repetido 00720 insertAVL( T, 1 ); assertTrue( 6 == T.size() ); 00721 insertAVL( T, 2 ); assertTrue( 6 == T.size() ); 00722 insertAVL( T, 5 ); assertTrue( 7 == T.size() ); 00723 insertAVL( T, 16 ); assertTrue( 7 == T.size() ); 00724 insertAVL( T, 50 ); assertTrue( 8 == T.size() ); 00725 insertAVL( T, 6 ); assertTrue( 9 == T.size() ); 00726 insertAVL( T, 13 ); assertTrue( 10 == T.size() ); 00727 insertAVL( T, 16 ); assertTrue( 10 == T.size() ); 00728 00729 watch = TestCase::toString( T ); assertFalse_Msg( "deleteBalanceAVL() ==> BEGIN" , "" ); 00730 deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T ); 00731 deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T ); 00732 deleteBalanceAVL( T, 8 ); assertTrue( isAVL(T) ); assertTrue( 8 == T.size() ); watch = TestCase::toString( T ); 00733 deleteBalanceAVL( T, 4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T ); 00734 deleteBalanceAVL( T, 4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T ); 00735 deleteBalanceAVL( T, 2 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); watch = TestCase::toString( T ); 00736 deleteBalanceAVL( T, 1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T ); 00737 deleteBalanceAVL( T, 3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T ); 00738 deleteBalanceAVL( T, 3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T ); 00739 watch = TestCase::toString( T ); assertFalse_Msg( "deleteBalanceAVL() ==> END" , "" ); 00740 } 00741 { // A52512 00742 Bin_Tree<int> T; std::string watch; 00743 insertAVL( T, 4 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() ); 00744 insertAVL( T, 3 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() ); 00745 insertAVL( T, 2 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() ); 00746 insertAVL( T, 1 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() ); 00747 assertTrue( isAVL(T) ); 00748 watch = TestCase::toString( T ); 00749 assertTrue_Msg("T == (3 (2 (1)) (4))" , "(3 (2 (1)) (4))" == TestCase::toString(T) ); 00750 00751 T.clear(); 00752 insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() ); 00753 insertAVL( T, 8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() ); 00754 insertAVL( T, 4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() ); 00755 insertAVL( T, 2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() ); 00756 insertAVL( T, 1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); 00757 insertAVL( T, 3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); 00758 assertTrue_Msg( 00759 "6 == " + TestCase::toString(T.size()) + " [T.size()]", 00760 6 == T.size() 00761 ); 00762 watch = TestCase::toString( T ); 00763 00764 // se prueba que no existe inserción de un elemento ya repetido 00765 insertAVL( T, 1 ); assertTrue( 6 == T.size() ); 00766 insertAVL( T, 2 ); assertTrue( 6 == T.size() ); 00767 insertAVL( T, 5 ); assertTrue( 7 == T.size() ); 00768 insertAVL( T, 16 ); assertTrue( 7 == T.size() ); 00769 insertAVL( T, 50 ); assertTrue( 8 == T.size() ); 00770 insertAVL( T, 6 ); assertTrue( 9 == T.size() ); 00771 insertAVL( T, 13 ); assertTrue( 10 == T.size() ); 00772 insertAVL( T, 16 ); assertTrue( 10 == T.size() ); 00773 00774 int izq = altura ( T.left() ) ; 00775 int der = altura ( T.right() ) ; 00776 assertTrue( T.data() == 4 ); // si esta balanceado 4 es la raiz 00777 // asi se prueba que la funcion balancear funciona. 00778 if (izq > der) { 00779 assertTrue( (izq - der) < 2 ); // la diferencia puede ser de 1 o 0. 00780 assertTrue( (izq - der) > 0 ); // pues es la condicion de un AVL 00781 } 00782 if (izq < der) { 00783 assertTrue( (der - izq) < 2 ); // la diferencia puede ser de 1 o 0. 00784 assertTrue( (der - izq) > 0 ); // pues es la condicion de un AVL 00785 } 00786 } 00787 { // A52512 00788 Bin_Tree<int> T; 00789 orderedInsert( T, 7 ); assertTrue( isAscending(T) ); 00790 orderedInsert( T, 5 ); assertTrue( isAscending(T) ); 00791 orderedInsert( T, 4 ); assertTrue( isAscending(T) ); 00792 orderedInsert( T, 8 ); assertTrue( isAscending(T) ); 00793 orderedInsert( T, 6 ); assertTrue( isAscending(T) ); 00794 orderedInsert( T, 3 ); assertTrue( isAscending(T) ); 00795 assertTrue( ! isAVL(T) ); assertTrue( 6 == T.size() ); 00796 std::string watch1 = TestCase::toString( T ); 00797 balanceAVL(T); // se prueba la funcion para balancear 00798 std::string watch2 = TestCase::toString( T ); 00799 assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); 00800 assertTrue_Msg( watch1 + " != " + watch2 , watch1 != watch2 ); 00801 assertTrue( isAscending(T) ); 00802 } 00803 if (false) { // es feo usar "cout" porque se mancha la pantalla 00804 using std::cout; using std::endl; 00805 Bin_Tree<int> T; 00806 cout <<"Insercion Ordenada de elementos :"<< endl; 00807 00808 orderedInsert( T, 7 ); 00809 orderedInsert( T, 5 ); 00810 orderedInsert( T, 4 ); 00811 orderedInsert( T, 8 ); 00812 orderedInsert( T, 6 ); 00813 orderedInsert( T, 3 ); 00814 00815 cout << "La raiz y los dos hijos del arbol antes de ser balanceado:"; 00816 cout << "valor de la raiz :" << T.data()<<"\n"; 00817 cout << "valor del hijo izquierdo :" << T.left().data()<<"\n"; 00818 cout << "valor del hijo derecho :" << T.right().data()<<"\n"; 00819 00820 balanceAVL(T); // se prueba la funcion para balancear 00821 cout << "\nArbol despues de ser enviado a la funcion balancear()\n"; 00822 00823 IPD( cout, T ); 00824 00825 cout << "\nraiz despues del balanceo: " << T.data(); 00826 cout << "\nhijo izquierdo despues del balanceo: " << T.left().data(); 00827 cout << "\nhijo derecho despues del balanceo :" << T.right().data(); 00828 cout << "\nEl arbol original cambia debido a que primero se usa una\n"; 00829 cout << "insercion normal de arboles binarios y luego queda como si\n"; 00830 cout << "se hubieran insertado los elementos con un metodo AVL de insercion.\n"; 00831 IPD( cout, T ); 00832 } 00833 00834 { // Permutaciones 00835 Bin_Tree<int> T; // Arbol en el que se insertarán varios valores 00836 const unsigned MAX_VALUES = 7; // cantidad máxima de nodos insertados en "T" 00837 std::vector< int > vec, ORIGINAL; 00838 for ( unsigned i=0; i<MAX_VALUES; ++i ) { 00839 ORIGINAL.push_back(i); 00840 } 00841 00842 std::string T_str; 00843 for ( unsigned N=0; N<MAX_VALUES; ++N ) { 00844 // prueba con todos los tamaños de árbol 00845 unsigned i, N_Fact = 1; // El factorial de N 00846 for (i = 1; i < N; ++i) { 00847 N_Fact *= i; 00848 } 00849 vec = ORIGINAL; 00850 for (unsigned i=0; i<N_Fact; ++i ) { 00851 // Siguiente secuencia desordenada de números 00852 next_permutation( vec.begin(), vec.end() ); 00853 T_str = "["; 00854 for ( std::vector<int>::size_type k=0; k<vec.size(); ++k ) { 00855 T_str += ' ' + TestCase::toString(vec[k]); 00856 } 00857 T_str += " ] ==> "; 00858 T.clear(); 00859 typename std::vector< int >::const_iterator it = vec.begin(); 00860 for ( unsigned j=0; j<N; ++j,++it ) { 00861 insertAVL( T , *it ); 00862 } 00863 /// Verifica que el árbol está balanceado 00864 assertTrue_Msg( T_str + "isAVL( "+TestCase::toString( T )+" )" , isAVL(T) ); 00865 if ( false && (failureCount() > 50) ) { 00866 return; // se sale para no generar demasidos errores 00867 } 00868 assertTrue_Msg( T_str + " T.size() == " + TestCase::toString( T.size() ), T.size() == N ); 00869 } 00870 } 00871 } 00872 } 00873 00874 /** Verifica que las funciones \c height() y \c depth() funcionan correctamente. 00875 \code 00876 a 00877 / \ 00878 / \ 00879 b e 00880 / \ / \ 00881 f h i k 00882 / \ 00883 l m 00884 / \ 00885 n o 00886 \endcode 00887 */ 00888 template <class E> 00889 void test_Bin_Tree<E>::test_heightdepth() { 00890 Bin_Tree<E> T = make_ab_no(); 00891 assertTrue( 4 == height( T.root() ) ); 00892 assertTrue( 0 == depth( T.root() ) ); 00893 00894 Bin_Tree<E> e = T.right(); 00895 assertTrue( 3 == height( e ) ); 00896 assertTrue( 1 == depth( e ) ); 00897 00898 Bin_Tree<E> b = T.left(); 00899 assertTrue( 1 == height( b ) ); 00900 assertTrue( 1 == depth( b ) ); 00901 00902 assertTrue( -1 == depth( Bin_Tree<E>() ) ); 00903 assertTrue( -1 == height( Bin_Tree<E>() ) ); 00904 } 00905 00906 using std::cout; 00907 using std::endl; 00908 00909 /// Verifica que \c make_FBHCID() construyó el árbol correctamente. 00910 template <class E> 00911 void test_Bin_Tree<E>::do_cout() { 00912 Bin_Tree<char> T1,T2 = make_FBHCID(); 00913 copyDeep( T1, T2 ); 00914 mirror( T2.left() ); // Tmp = T2.left(); mirror( Tmp ); 00915 mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp ); 00916 cout << endl << "homomorfo()" << endl; 00917 IPD( cout , T1 ); cout << endl; 00918 IPD( cout , T2 ); cout << endl; 00919 } 00920 00921 /// Programa principal desde donse se invocan todas las pruebas 00922 int main() { 00923 if (1) { 00924 cout << "test_Bin_Tree<char>\n"; 00925 test_Bin_Tree<char> tester; 00926 tester.run(); 00927 cout << tester.report(); 00928 } 00929 } 00930 00931 // EOF: test_Bin_Tree.cpp
