Algoritmos Árbol y Nodos

Definiciones simples.
En informática, un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

Definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Árbol

Un árbol es una estructura de datos ampliamente usada que emula la forma de un
árbol (un conjunto de nodos conectados).

Nodo, es la unidad sobre la que seconstruye el árbol y puede tener cero o más nodos hijos conectados a él.

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.
En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre: nodo que contiene un puntero al nodo actual.
En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

En cuanto a la posición dentro del árbol

Nodo raíz: nodo que no tiene padre.Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Nodo rama: estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Un árbol en el que en cada nodo o bien todos o ninguno de loshijos existe, se llama árbol completo.

[pic]

En relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol.

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Asísucesivamente.

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel.

Definición de árbol binario.

Un árbol binario esta caracterizado por ser de grado 2, todo nodo del árbol tiene un subárbol binario izquierdo y derecho asociados

Árbol Binario Completo o Lleno: todos sus nodos,
excepto las hojas, tienen siempre dos hijos (el subárbol izquierdo y el derecho) no nulos. Elnúmero de nodos de un árbol completo se calcula por la fórmula: Número de nodos =2h-1 (donde h es la altura)

Árbol Binario Completo de Altura o Profundidad H: Es un árbol Binario Completo en donde todas las hojas están en el nivel H.

Hay dos formas tradicionales de representar un árbol binario en memoria: como variables dinámicas o listas.

Definición de árbol binario de búsqueda.

Unárbol binario de búsqueda es un árbol binario en el cual cada nodo cumple con que todos los nodos de su subárbol izquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz.

Un ejemplo de árbol binario de búsqueda es el siguiente:
[pic]

Operaciones sobre árboles binarios de búsqueda.
Salvo que trabajemos con árboles especiales, las inserciones seránsiempre en punteros de nodos hoja o en punteros libres de nodos rama.

Adición de un nodo.
Al insertar elementos en un árbol será necesario tener en cuenta lo siguiente.
En el árbol binario cada nodo puede tener hasta dos hijos cada uno con un valor de clave. El valor de clave del subárbol izquierdo es menor o igual que los valores del árbol derecho.

Procedimiento
• Compararse la clave ainsertar con la raíz del árbol. Si es mayor, debe avanzarse hacia el subárbol derecho. Si es menor, debe avanzarse hacía el subárbol izquierdo.

• Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes condiciones:

1. El subárbol derecho es igual a vacío, o el subárbol izquierdo es igual a vacío, en cuyo caso se procede a insertar el elemento en el lugar que lecorresponde.

2. La clave que quiere insertarse es igual a la raíz del árbol, en cuyo caso no se realiza la inserción.

Borrado de nodos en árboles binarios.
1. Busco el nodo a borrar.
2. Si el nodo es hoja basta con que su padre haga referencia a nodo vacío.
3. Si no es nodo hoja habrá que sustituirlo por otro bajo las siguientes condiciones:
a. El nodo a borrar solo tiene un hijo y...