Arboles

Árboles binarios de búsqueda (ABB)
Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor del nodo raíz del subárbol izquierdo es menor que el valor del nodo raíz y que el valor del nodo raíz del subárbol derecho es mayor que el valor del nodo raíz.

Operaciones en ABB.  
El conjunto de operaciones que se pueden realizar sobre un ABB es similar al que se realizasobre otras estructuras de datos, más alguna otra propia de árboles:
* Buscar un elemento.
* Insertar un elemento.
* Eliminar un elemento.
* Movimientos a través del árbol:
* Izquierda.
* Derecha.
* Raíz.
* Información:
* Comprobar si un árbol está vacío.
* Calcular el número de nodos.
* Comprobar si el nodo es hoja.
*Calcular el nivel de un nodo.
* Calcular la altura de un árbol.
Buscar un elemento.
Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva como:
* Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.
* Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito.
* Si elvalor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
* Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.
El valor de retorno de una función de búsqueda en un ABB puede ser un puntero al nodo encontrado, o NULL, si no se ha encontrado.
Insertar un elemento.
Para insertar unelemento nos basamos en el algoritmo de búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no lo está, lo insertaremos a continuación del último nodo visitado. Para ello, se necesita un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.
* Padre = NULL
* nodo = Raiz
* Bucle: mientras actual no sea unárbol vacío o hasta que se encuentre el elemento.
* Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo:
Padre=nodo, nodo=nodo->izquierdo.
* Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho:
Padre=nodo, nodo=nodo->derecho.
* Si nodo no es NULL, elelemento está en el árbol, por lo tanto salimos.
* Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.
* Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.
* Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como unnuevo árbol derecho de Padre.
Este modo de actuar asegura que el árbol sigue siendo ABB.
Eliminar un elemento.
Para eliminar un elemento también nos basamos en el algoritmo de búsqueda. Si el elemento no está en el árbol no lo podremos borrar. Si está, hay dos casos posibles:
1. Se trata de un nodo hoja: en ese caso lo borraremos directamente.
2. Se trata de un nodo rama: en ese caso nopodemos eliminarlo, puesto que perderíamos todos los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos sus valores. A continuación eliminamos el nodo hoja.
Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valorinicial para ese puntero es NULL.
* Padre = NULL
* Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.
* (*) Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:
* El nodo raíz es un nodo hoja:
* Si 'Padre' es NULL, el nodo raíz es el único del árbol, por...