arboles binarios final

7/23/2019 Arboles Binarios Final

1/8

Arboles binariosUn rbol es una estructura dinmica no lineal ; Se define como una estructura homognea de tipo T con un

nmero finito de rboles disjuntos llamados subrboles

-las caractersticas de un rbol

a) Todo rbol que no es vaco tiene un nico nodo de raz

b) un nodo x es descendiente directo de un nodo Y x es hijo de Y

c) un nodo x es un antecesor de un nodo Y

x es padre de y

d) todos los hijos descendientes de un solo nodo son hermanos

c) todo nodo que no tiene nodos descendientes se denominan NODO DE HOJA o TERMINAL

f) todo no que no es raz ni terminal es un Nodo Interior

g) GRADO es el NMERO de descendientes directos que tiene un nodo

h) GRADO DEL RBOL es el mximo grado de todos los nodos de rbol

i) Nivel es el nmero de arcos que deben ser recorridos para llegar a un determinado nodo

j) Altura del rbol es el mximo nmero de niveles de todo el nodo del rbol

rboles Binarios

Un rbol binario cada nodo puede tener como mximo dos subrboles y siempre es necesario distinguir entre

el subrbol izquierdo y el subrbol derecho

rbol binario tipo T es una estructura homognea que es la concatenacin de un elemento tipo T, llamado raz,

con dos rboles binarios disjuntos, llamados subrbol izquierdo y subrbol derecho.

Se pueden aplicarpara representar un arbol genealgico o para representar expresiones algebraicas

construidas con operadores binarios

Distintos. Cuando sus estructuras son diferentes

Similares. Cuando sus estructuras son idnticas pero la informacin que contiene cada rbol es diferente.

Equivalentes. Cuando son similares y adems la informacin es idntica entre los dos rboles.

Se dice que un rbol binario est llenosi es un rbol binario de profundidad k que tiene (2^k) - 1 nodos. Unrbol binario lleno es aquel que contiene el nmero mximo de posibles nodos. Como en estos casos no existen

subrboles vacos excepto para los nodos terminales.

Un rbol binario con n nodos y profundidad k se dice que es completosi y slo si sus nodos se corresponden

con los nodos numerados de 1 a n en el rbol binario lleno de profundidad k. Definimos un rbol binario

completo (ABC) como un A .B .lleno pero con sus hojas dispuestas de tal manera que las hojas del nivel ms bajo

estn situadas tan a la izquierda como sea posible.


2/8

Recorridos sistemticos.Una de las operaciones ms importantes que se realiza en un rbol binario es el recorrido de los mismos. Recorrersignifica visitar los nodos del rbol en forma ordenada, de tal manera que todos los nodos del mismo seanvisitados una sola vez. Existen tres formas diferentes de efectuar el recorrido y todas Ellas de naturaleza recursiva;estas son:a) Recorrido en preorden

Visitar la raz

Recorrer el subrbol izquierdoRecorrer el subrbol derecho

b) Recorrido en inordenRecorrer el subrbol izquierdoVisitar la razRecorrer el subrbol derecho

c) Recorrido en PosordenRecorrer el subrbol izquierdoRecorrer el subrbol derechoVisitar la raz

ProcedimientoComenc creando la clase nodo que define un nodo como un tipo de dato que contiene 1 dato y susrespectivas 2 conexiones (izquierda y derecha)

Despus se comenz definir la clase rbol Binario en la cual damos los parmetros iniciales como establecer la

raz del rbol a nulo y definir los mtodos de escritura

Mtodos de recorrido en mi caso defin 3 metodos de recorrido los cules sonrecursivos

publicvoidRPreOrden(Nodoraiz) {

if(raiz== null) {

return;}System.out.println(raiz.getValor());

RPreOrden(raiz.getIzquierda());

RPreOrden(raiz.getDerecha());

}

publicvoidRInOrden(Nodoraiz) {

if(raiz== null) {

return;}RInOrden(raiz.getIzquierda());

System.out.println(raiz.getValor());RInOrden(raiz.getDerecha());

}

publicvoidRPosOrden(Nodoraiz){if(raiz== null) {

return;

}RPosOrden(raiz.getIzquierda());RPosOrden(raiz.getDerecha());

System.out.println(raiz.getValor());

}


3/8

Ejemplo de ejecucinUn ejemplo de ejecucin del programa son los 2 siguientes el primero es creando un rbol con nmeros

Donde el rbol quedara de la siguiente forma

De acuerdo a los datos introducidos por teclado

Recorrido en pre orden Recorrido Inorden Recorrido Pos orden


4/8

ARBOL DE STRINGS

Recorrido en pre orden Recorrido Inorden Recorrido Pos orden


5/8

Bsqueda en un rbol:El algoritmo de busque principalmente visita la raz de este, si el elemento que

buscamos est en la raz entonces la bsqueda termina pero si no, si es ms

grande visita primero el subrbol derecho y si es ms chico visita el subrbol

izquierdo principalmente se usa de manera recursiva ya que necesitamos visitarel mismo rbol aunque tambin se puede hacer de forma iterativa

O en forma de seudocdigo

boolean buscar(tarbol *a, elem)

{

if (a == NULL) return FALSE;

else if (a->clave < elem) return buscar(a->der, elem);

else if (a->clave > elem) return buscar(a->izq, elem);

else return TRUE;

}

*/////*arbol creado*//////*

recorrido PreOrdenHola

estoes

un

rbol*/////* recorrido InOrden */////*

esarbol

unesto

Hola*/////recorrido PosOrden*/////

arbol

un

esesto

Hola*/////buscando en el rbol el nodo esto*/////

comprobacion exitosa se encontro el Nodo:esto

Ejemplo de ejecucin


6/8

Insercin en un rbol:

Para insertar un elemento nos basamos en el algoritmo de bsqueda. Si el elemento est enel rbol no lo insertaremos. Si no lo est, lo insertaremos a continuacin del ltimo nodo

visitado.

Necesitamos un puntero auxiliar paraconservar una referencia al padre del nodoraz actual. El valor inicial para ese puntero esNULL.

RAIZ = NULL

nodo = Raiz

Bucle: mientras actual no sea un rbol vaco o

hasta que se encuentre el elemento.

Si el valor del nodo raz es mayor que el

elemento que buscamos, continuaremos labsqueda en el rbol izquierdo:RAIZ=nodo,

nodo=nodo->izquierdo.

Si el valor del nodo raz es menor que el

elemento que buscamos, continuaremos la

bsqueda en el rbol derecho: Padre=nodo,

nodo=nodo->derecho.

Si nodo no es NULL, el elemento est en el

rbol, por lo tanto salimos.

Si RAIZ es NULL, el rbol estaba vaco, por lo

tanto, el nuevo rbol slo contendr el nuevo

elemento, que ser la raz del rbol.

Si el elemento es menor que la RAIZ, entonces

insertamos el nuevo elemento como un nuevo

rbol izquierdo de RAIZ.

Si el elemento es mayor que la RAIZ, entonces

insertamos el nuevo elemento como un nuevo

rbol derecho de la RAIZ.


recorrido PreOrdenHola

estoes

un

rbol*/////* recorrido InOrden

esarbol

unesto

Hola*/////recorrido PosOrden*/////

arbol

un

esesto

Hola*/////buscando en el rbol el nodo esto*///

comprobacion exitosa se encontro el Nodo:esto*/////*insertando el nodo : exito*/////*

*/////*recorrido PreOrden*/////*

Holaesto

es

unarbol

exito

Ejemplo de ejecucin


7/8

Borrado en un rbolPueden darse tres casos, una vez encontrado el nodo a borrar:1) El nodo no tiene descendientes.Simplemente se borra.2) El nodo tiene al menos un descendiente por una sola

rama.Se borra dicho nodo, y su primer descendiente se asigna como hijo delpadre del nodo borrado.3) El nodo tiene al menos un descendiente por cada rama.

Al borrar dicho nodo es necesariomantener la coherencia de losenlaces, adems de seguirmanteniendo la estructura comoun rbol binario de bsqueda. Lasolucin consiste en sustituir lainformacin del nodo que se borra

por el de una de las hojas, y borrara continuacin dicha hoja

void borrar(tarbol **a, int elem)

{

void sustituir(tarbol **a, tarbol **aux);

tarbol *aux;

if (*a == NULL) /* no existe la clave (paso

inductivo)*/

return;

if ((*a)->clave < elem) borrar(&(*a)->der,elem);

else if ((*a)->clave > elem) borrar(&(*a)-

>izq, elem);

else if ((*a)->clave == elem) {

aux = *a;

if ((*a)->izq == NULL) *a = (*a)->der;

else if ((*a)->der == NULL) *a = (*a)-

>izq;

else sustituir(&(*a)->izq, &aux); /* se

sustituye por

la mayor de las menores */

free(aux);//liberamos la memoriaque usamos con el auxiliar

}


recorrido PreOrden

Holaesto

esun

rbol*/////* recorrido InOrden

esarbol

unesto

Hola

*/////recorrido PosOrden*/////

arbolun

esesto

Hola*/////buscando en el rbol el nodo esto*/////

comprobacion exitosa se encontro el Nodo:esto*/////*insertando el nodo : exito*/////*

*/////*recorrido PreOrden*/////*Hola

estoes

unarbol

xito

*/////*eliminando el nodo: es*/////*

*/////*recorrido PreOrden*/////*

Holaesto

unarbol

xito

Ejemplo de ejecucin


8/8

Los arboles binarios son estructuras que no sirven para manejar de forma muy eficiente , la verdad es que me

han gustado ms en cuanto a listas doblemente ligadas u otro tipo de estructuras ya que son muy eficientes en

la hora de buscar informacin, eliminar e insertar nuevos nodos cosas que no ocurre en otras estructuras ,el

nico inconveniente que le veo es que a la hora de crear el rbol no tenemos muchas opciones en cuanto a l

orden de introducir la informacin fuera de eso me parecen bastante eficientes

arboles binarios final

Documents