Arbol
Páginas: 5 (1229 palabras)
Publicado: 22 de abril de 2015
// Programa de prueba de la clase Arbol.
#include
#include
using namespace std;
// declaración anticipada de la clase Arbol
class Arbol;
// definición de la plantilla de clase NodoArbol
class NodoArbol{
friend class Arbol;
private:
NodoArbol *izquierdoPtr; // apuntador al subárbol izquierdo
int datos;
NodoArbol *derechoPtr; // apuntador al subárbol derechopublic:
// constructor
NodoArbol( const int &d )
: izquierdoPtr( 0 ), // apuntador al subárbol izquierdo
datos( d ), // datos del nodo del árbol
derechoPtr( 0 ) // apuntador al subárbol derecho
{
// cuerpo vacío
} // fin del constructor de NodoArbol
// devuelve una copia de los datos del nodo
int obtenerDatos() const { return datos; } //fin de la función obtenerDatos
}; //
// definición de la plantilla de clase Arbol
class Arbol{
private:
NodoArbol *raizPtr;
// funciones utilitarias
void ayudanteInsertarNodo( NodoArbol **, const int & );
void ayudantePreOrden( NodoArbol * ) const;
void ayudanteInOrden( NodoArbol * ) const;
void ayudantePostOrden( NodoArbol * ) const;
public:
Arbol(); // constructor
voidinsertarNodo( const int & );
void recorridoPreOrden() const;
void recorridoInOrden() const;
void recorridoPostOrden() const;
}; // fin de la clase Arbol
// constructor
Arbol::Arbol(){
raizPtr = 0; // indica que al principio el árbol está vacío
} // fin del constructor de Arbol
// inserta el nodo en el Arbol
void Arbol::insertarNodo( const int &valor ){
ayudanteInsertarNodo(&raizPtr, valor );
} // fin de la función insertarNodo
// función utilitaria llamada por insertarNodo; recibe un apuntador a un apuntador, para que la función pueda modificar el valor del apuntador
void Arbol::ayudanteInsertarNodo(NodoArbol **ptr, const int &valor ){
// el subárbol está vacío; crea nuevo NodoArbol que contiene el valor
if ( *ptr == 0 )
*ptr = new NodoArbol( valor );else // el subárbol no está vacío
{
// los datos a insertar son menores que los datos en el nodo actual
if ( valor < ( *ptr )->datos )
ayudanteInsertarNodo( &( ( *ptr )->izquierdoPtr ), valor );
else{
// los datos a insertar son mayores que los datos en el nodo actual
if ( valor > ( *ptr )->datos )
ayudanteInsertarNodo( &( ( *ptr)->derechoPtr ), valor );
else // se ignora el valor de datos duplicado
cout << valor << " dup" << endl;
} // fin de else
} // fin de else
} // fin de la función ayudanteInsertarNodo
// empieza el recorrido preorden del Arbol
void Arbol::recorridoPreOrden() const{
ayudantePreOrden( raizPtr );
} // fin de la función recorridoPreOrden
// función utilitaria para realizarel recorrido preorden del Arbol
void Arbol::ayudantePreOrden( NodoArbol *ptr ) const{
if ( ptr != 0 )
{
cout << ptr->datos << ' '; // procesa el nodo
ayudantePreOrden( ptr->izquierdoPtr ); // recorre el subárbol izquierdo
ayudantePreOrden( ptr->derechoPtr ); // recorre el subárbol derecho
} // fin de if
} // fin de la función ayudantePreOrden
// empieza el recorridoinorden del Arbol
void Arbol::recorridoInOrden() const{ ayudanteInOrden( raizPtr );
} // fin de la función recorridoInOrden
// función utilitaria para realizar el recorrido inorden del Arbol
void Arbol::ayudanteInOrden( NodoArbol *ptr ) const{
if ( ptr != 0 ){
ayudanteInOrden( ptr->izquierdoPtr ); // recorre el subárbol izquierdo
cout << ptr->datos << ' '; // procesa el nodoayudanteInOrden( ptr->derechoPtr ); // recorre el subárbol derecho
} // fin de if
} // fin de la función ayudanteInOrden
// empieza el recorrido postorden del Arbol
void Arbol::recorridoPostOrden() const{
ayudantePostOrden( raizPtr );
} // fin de la función recorridoPostOrden
// función utilitaria para realizar el recorrido postorden del Arbol
void Arbol::ayudantePostOrden(...
#include
#include
using namespace std;
// declaración anticipada de la clase Arbol
class Arbol;
// definición de la plantilla de clase NodoArbol
class NodoArbol{
friend class Arbol;
private:
NodoArbol *izquierdoPtr; // apuntador al subárbol izquierdo
int datos;
NodoArbol *derechoPtr; // apuntador al subárbol derechopublic:
// constructor
NodoArbol( const int &d )
: izquierdoPtr( 0 ), // apuntador al subárbol izquierdo
datos( d ), // datos del nodo del árbol
derechoPtr( 0 ) // apuntador al subárbol derecho
{
// cuerpo vacío
} // fin del constructor de NodoArbol
// devuelve una copia de los datos del nodo
int obtenerDatos() const { return datos; } //fin de la función obtenerDatos
}; //
// definición de la plantilla de clase Arbol
class Arbol{
private:
NodoArbol *raizPtr;
// funciones utilitarias
void ayudanteInsertarNodo( NodoArbol **, const int & );
void ayudantePreOrden( NodoArbol * ) const;
void ayudanteInOrden( NodoArbol * ) const;
void ayudantePostOrden( NodoArbol * ) const;
public:
Arbol(); // constructor
voidinsertarNodo( const int & );
void recorridoPreOrden() const;
void recorridoInOrden() const;
void recorridoPostOrden() const;
}; // fin de la clase Arbol
// constructor
Arbol::Arbol(){
raizPtr = 0; // indica que al principio el árbol está vacío
} // fin del constructor de Arbol
// inserta el nodo en el Arbol
void Arbol::insertarNodo( const int &valor ){
ayudanteInsertarNodo(&raizPtr, valor );
} // fin de la función insertarNodo
// función utilitaria llamada por insertarNodo; recibe un apuntador a un apuntador, para que la función pueda modificar el valor del apuntador
void Arbol::ayudanteInsertarNodo(NodoArbol **ptr, const int &valor ){
// el subárbol está vacío; crea nuevo NodoArbol que contiene el valor
if ( *ptr == 0 )
*ptr = new NodoArbol( valor );else // el subárbol no está vacío
{
// los datos a insertar son menores que los datos en el nodo actual
if ( valor < ( *ptr )->datos )
ayudanteInsertarNodo( &( ( *ptr )->izquierdoPtr ), valor );
else{
// los datos a insertar son mayores que los datos en el nodo actual
if ( valor > ( *ptr )->datos )
ayudanteInsertarNodo( &( ( *ptr)->derechoPtr ), valor );
else // se ignora el valor de datos duplicado
cout << valor << " dup" << endl;
} // fin de else
} // fin de else
} // fin de la función ayudanteInsertarNodo
// empieza el recorrido preorden del Arbol
void Arbol::recorridoPreOrden() const{
ayudantePreOrden( raizPtr );
} // fin de la función recorridoPreOrden
// función utilitaria para realizarel recorrido preorden del Arbol
void Arbol::ayudantePreOrden( NodoArbol *ptr ) const{
if ( ptr != 0 )
{
cout << ptr->datos << ' '; // procesa el nodo
ayudantePreOrden( ptr->izquierdoPtr ); // recorre el subárbol izquierdo
ayudantePreOrden( ptr->derechoPtr ); // recorre el subárbol derecho
} // fin de if
} // fin de la función ayudantePreOrden
// empieza el recorridoinorden del Arbol
void Arbol::recorridoInOrden() const{ ayudanteInOrden( raizPtr );
} // fin de la función recorridoInOrden
// función utilitaria para realizar el recorrido inorden del Arbol
void Arbol::ayudanteInOrden( NodoArbol *ptr ) const{
if ( ptr != 0 ){
ayudanteInOrden( ptr->izquierdoPtr ); // recorre el subárbol izquierdo
cout << ptr->datos << ' '; // procesa el nodoayudanteInOrden( ptr->derechoPtr ); // recorre el subárbol derecho
} // fin de if
} // fin de la función ayudanteInOrden
// empieza el recorrido postorden del Arbol
void Arbol::recorridoPostOrden() const{
ayudantePostOrden( raizPtr );
} // fin de la función recorridoPostOrden
// función utilitaria para realizar el recorrido postorden del Arbol
void Arbol::ayudantePostOrden(...
Leer documento completo
Regístrate para leer el documento completo.