Problemas con árboles binarios

[avechuche]

Hola gente, necesito ayuda (De esto depende si apruebo o no Programación II ^^)

Tengo que hacer 5 ejercicios si o si (Además de aprobar el final) para aprobar la materia. Hice los 3, pero los otros dos no tengo ni idea (Al menos de uno)

1) Tengo que crear un algotirmo recursivo o no, que me permita construir un árbol binario de búsqueda a partir de un árbol binario.
2) Tengo que crear una función que me diga si un árbol es binario de búsqueda.

Les dejo el TAD que usamos, por si quieren intentar con ellos, o si tienen otros, desp me las arreglo para transformalo.
Procedure CrearArbolNulo(Var A: Arbol);
Function ArbolNulo(A: Arbol): Boolean; // Sinonimo de arbol vacio
Function ArbolLleno(A: Arbol): Boolean;
Function RamaNula(P: PosicionArbol): Boolean; // Controla si un apuntador es nil
Function RecuperarDatos(A: Arbol; P: PosicionArbol; Var X: TipoElemento): Boolean;
Function CargarArbol(Var A: Arbol): Boolean;
Function PreOrden(A: Arbol): String;
Function InOrden(A: Arbol): String;
Function PostOrden(A: Arbol): String;
Function Anchura(A: Arbol): String;
Function PreOrdenITE(A: Arbol): String;
Function Altura(A: Arbol): Integer;
Function BuscarPreOrden(A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): PosicionArbol;
Function Nivel(A: Arbol; Q:PosicionArbol): Integer;
Function HijoIzquierdo(A: Arbol; P: PosicionArbol): PosicionArbol;
Function HijoDerecho(A: Arbol; P: PosicionArbol): PosicionArbol;
Function Padre(A: Arbol; Hijo: PosicionArbol): PosicionArbol;
// Busqueda Binaria
Function InsertarNodo(Var A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): Boolean;
Function EliminarNodo(Var A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): Boolean;
Function BusquedaBinaria(A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): PosicionArbol;
// Busqueda Binaria Balanceado
Function InsertarNodoAVL(Var A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): Boolean;
Function EliminarNodoAVL(Var A: Arbol; X: TipoElemento; ComparaPor:CampoComparar): Boolean;

[Casimiro Notevi]

¿Y qué tienes hecho?
Una simple búsqueda en google te devuelve montones de ejemplos, ¿no te vale ninguno?

[avechuche]

El que tenia que comprobar si es un árbol binario de búsqueda, ya lo resolvi, ese era el que tenia casi echo, pero me daba ciertos errores, el que me falta ahora, es pasar de un árbol binario a un árbol binario de búsqueda, ese si que no se como empezarlo! Ya busque en Google a ver si hay algun algoritmo echo, pero nada, ni parecido, como si nadie pasara de arbol a ABB ^^.

[Casimiro Notevi]

pasar de un árbol binario a un árbol binario de búsqueda

La verdad es que no entiendo la pregunta :confused:

[nlsgarcia]

avechuche,


...crear una función que me diga si un árbol es binario de búsqueda...


Revisa estos links:

Árbol binario de búsqueda : http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda

Arboles Binarios : http://www.algoritmia.net/articles.php?id=17&leng=Pascal

Árbol binario de búsqueda en Pascal : http://tutorialesnet.net/blog/98-programacion/general/89-arbol-binario-de-busqueda-en-pascal

Manejo de arboles binarios : http://ejemplos.mis-algoritmos.com/manejo-de-arboles-binarios

Algoritmos en Pascal : http://antares.sip.ucm.es/cpareja/libroAlgoritmos/docs/libro-completo.pdf
Espero sea útil :)

Nelson.

[avechuche]

La verdad es que no entiendo la pregunta :confused:

Claro es asi. Un árbol binario, significa que cada nodo puede tener 0, 1 ó 2 hijos, por eso binario. Pero no necesariamente es de busqueda. Un árbol de busqueda es cuando los hijos izquierdos son menores que el padre y los derechos son mayores.

Un ejemplo facil 4 <= 5 => 6. Ahi 5 es la raíz del árbol, 4 es el hijo izquierdo y es menor que la raíz y 6 es el hijo derecho y es mayor que la raíz. Este es un árbol binario de busqueda.

Ahora 5 <= 4 => 6, esto es un árbol binario, pero no de busqueda, porque la raíz que es 4 es menor que el hijo izquierdo.

Entonces yo tengo que generar un algoritmo que pase de arbol binario NO de busqueda a uno binario DE busqueda.

[avechuche]

avechuche,



Revisa estos links:
Espero sea útil :)

Nelson.

Gracias Nelson. La teoria la tengo clara, lo que pasa es que no me doy cuenta como hacerlo, y mas con el tema de recursividad que es algo que no se usa todos los dias :)

[nlsgarcia]

avechuche,


...La teoria la tengo clara...


Te sugiero revisar los links del Msg #5, en ellos encontraras código que te dará una mejor idea de como empezar tu proyecto, el último link en particular contiene mucha información sobre arboles binarios.

Espero sea útil :)

Nelson.