ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Implementación de un Árbol de búsqueda binaria en C++


Enviado por   •  23 de Febrero de 2017  •  Tarea  •  1.390 Palabras (6 Páginas)  •  308 Visitas

Página 1 de 6

/**

Marlon A. Espinosa Castañeiras

28-02-2013

Estructura: Árbol de Busqueda Binaria

Descripción: Sirve para introducir valores y buscar elementos en un árbol

en tiempo logaritmico, además estan implementadas las

funciones máximo, mínimo, sucesor, predecesor, borrar

elementos, buscar un elemento en el árbol, recorrido

Entre-Orden en un árbol y se expone como implementar los

demás recorridos, todo esto en tiempo O( log N ).

**/

#include <iostream>

#include <cassert>

#include <cstdlib>

#include <vector>

#include <algorithm>

using namespace std;

typedef int TDato;

vector <int> V;

struct TNodo{

TNodo* p;//Padre

TDato dato;//Nodo

TNodo* hi;//Hijo izquierdo

TNodo* hd;//Hijo derecho

};

typedef TNodo* TArbol;//puntero a un nodo del Arbol

TArbol InsertDato(TArbol& A, TDato x){

if (A == NULL){

A = new TNodo;//se crea espacio en memoria;

A -> dato = x;

A -> p = NULL;//se setea los hijos de el root en NULL y también el padre

A -> hi = NULL;

A -> hd = NULL;

}

else{

// se busca si es menor que el nodo analizado y se inserta en el subarbol que representa el hijo izquierdo

if (A -> dato >= x){

A -> hi = InsertDato(A -> hi, x);

A -> hi -> p = A;

}

//lo mismo pero buscando el mayor y se inserta en el subarbol derecho

else{

A -> hd = InsertDato(A -> hd, x);

A -> hd -> p = A;

}

}

return A;// se devuelve el árbol generado luego de la inserción

}/**OK**/

/***

Nota: Para los demás recorridos solo se necesita cambiar

la posición en la que se imprime el nodo.

***/

void EntreOrden(TArbol A){

/**** Recorriodo en Entre-Orden ****/

if (A == NULL)

return;

if (A -> hi != NULL)

EntreOrden(A -> hi);

cout << A -> dato << " ";

if (A -> hd != NULL)

EntreOrden(A -> hd);

}/**OK**/

TArbol Buscar(TArbol A, TDato x)

{

while (A != NULL && A -> dato != x){

/*si el buscado es menor que el nodo analizado busco en el subarbol izquierdo*/

if (x < A -> dato)

A = A -> hi;

/*si el buscado es mayor que el nodo analizado busco en el subarbol derecho*/

else

A = A -> hd;

}

if (A == NULL)

return NULL;

return A;

/** Implementación Recursiva de la busqueda**/

/* if(A == NULL)

return NULL;

if(A-> dato == x)

return A;

if(A -> dato > x)

return Buscar(A -> hi, x);

return Buscar(A -> hd, x);

*/

}/**OK**/

TArbol Minimo(TArbol A){

//Buscar el mínimo no es más que siempre cojer el nodo más

//a la izquierda mientras exista alguno

while( A -> hi != NULL)

A = A -> hi;

return A;

}/**OK**/

TArbol Maximo(TArbol A){

//Lo mismo que el mínimo pero buscando el más a la derecha

//minetras exista alguno

while(A -> hd != NULL)

A = A -> hd;

return A;

}/**OK**/

TArbol Sucesor(TArbol AA)

{

/*Si tiene hijo derecho busco en el subarbol derecho

el mínimo, ya que a la derecha del nodo están los mayores

que el me quedo con el mínimo de ellos

*/

if(AA -> hd != NULL)

return Minimo(AA -> hd);

TArbol y = AA -> p;

/*

Si no tiene hijo derecho voy intercambiando hijo con padre

y cuando el hijo no sea el hijo derecho del padre devuelvo el

padre y ese es el sucesor del nodo pedido.

*/

while(y != NULL && AA == y -> hd){

AA = y;

y = y -> p;

}

return y;

}/**OK**/

TArbol Predecessor(TArbol AA)

{

/*Si tiene hijo izquierdo busco en el subarbol derecho

el mínimo, ya que a la izquierda del nodo están los mayores

que el me quedo con el

...

Descargar como (para miembros actualizados) txt (7 Kb) pdf (52 Kb) docx (16 Kb)
Leer 5 páginas más »
Disponible sólo en Clubensayos.com