Implementación de un Árbol de búsqueda binaria en C++
Enviado por Kurapica • 23 de Febrero de 2017 • Tarea • 1.390 Palabras (6 Páginas) • 313 Visitas
/**
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
...