Árboles

Concepto de Árbol
En la computación, un árbol es una estructura de datos general y poderosa que
asemeja un árbol real.
Un árbol es un grafo acíclico (no posee caminos cerrados) en donde cualquier par de
nodos están conectados mediante un único camino.

Árbol con raíz (Árbol con raíz dirigido): Es un árbol orientado de manera que el resto de
los nodos se alejan del vértice raíz.
Un árbol con raíz es como una lista enlazada, tiene un primer nodo, pero este nodo
se hace llamar “nodo raíz” del árbol. Cada nodo dentro del árbol tiene un número
variable de punteros al siguiente, y estos punteros a siguiente referencian a otros
nodos dentro del árbol. Cada nodo dentro de un árbol, con la excepción de la raíz, tiene
exáctamente un nodo que apunta hacia él.
 Árbol binario
Un árbol binario es un árbol con raíz orientado en donde cada nodo tiene como
máximo 2 hijos, en donde se hacen llamar Hijo a izquierda e hijo a derecha.
Un arbol binario puede ser:
1. un arbol vacío (NULL).
2. Consiste de un nodo y dos subárboles binarios, el árbol derecho e izquierdo.
La estructura de cada nodo del árbol posee un puntero hacia un hijo a izquierda y
otro puntero hacia un hijo a derecha. Si ese nodo no posee un hijo a derecha o izquierda,
se le almacenará “NULL”.
 Definiciones
Raíz: Nodo sin padre. Todos los nodos
hijos se orientan hacia abajo.
Hijo: Hijo a izquierda o derecha de un
nodo
Padre: Nodo que apunta hacia los hijos.
Grado de un nodo: cantidad de hijos de
un nodo.
Hoja: Nodo que no posee hijos. (su grado
es 0)
Hermanos: Nodos que son hijos del
mismo padre.
Nodo Interno: Posee al menos hijo a
izquierda o a derecha. (su grado es
distinto de 0)
Grado de un árbol: Cantidad máxima de
hijos que posee un nodo del árbol.
Altura: 1 + Distancia de un nodo a la raíz.
Nivel: El nivel de un nodo esta definido
como la distancia entre un nodo y la raíz.
Profundidad de un árbol: Altura máxima.
Para el siguiente árbol, indicar: Raíz, nodos internos, nodos hoja, grado de cada
nodo, nivel, altura del árbol y profundidad:
Recorridos en un árbol binario
Preorder: Primero raíz, luego subárbol izquierdo y por último subárbol derecho.

Inorder: Primero subárbol izquierdo, luego raíz y subárbol derecho.

Posorder: Primero subárbol izquierdo, luego derecho, y por último la raíz.

Recorrer el árbol de la figura mediante los 3 recorridos:
Preorder, Inorder y Posorder.
Codificación
Creación de un Nodo árbol
nodoA* crearNodoArbol(int dato)
{
nodoA* nuevo= (nodoA*)malloc(sizeof(nodoA));
nuevo->dato=dato;
nuevo->izq=NULL;
nuevo->der=NULL;

return nuevo;
}
 Recorridos
void preorder(nodoA* A)
{
if (A)
{
printf(“%d ”,A->dato);←Muestra raíz antes de recorrer subárbol izq y der.
preorder(A->izq);
preorder(A->der);
}
}
 Recorridos
void inorder(nodoA* A)
{
if (A)
{
preorder(A->izq);
printf(“%d “,A->dato); ←- se imprime raíz luego de recorrer subárbol izq.
preorder(A->der);
}
}
 Recorridos
void posorder(nodoA* A)
{
if (A)
{
posorder(A->izq);
posorder(A->der);
printf(“%d “,A->dato); ←Imprime raíz luego de recorrer subárbol izq. y der.
}
}
 int buscarDato(nodoA* A, int dato)
{
int enc=0;
if (A)
{
if (A->dato != dato)
Buscar un dato en un {

árbol binario
enc= buscarDato(A->izq,dato)
if (!enc)
enc=buscarDato(A->der,dato);
}
else
enc=1;
}
return enc;
}
 Buscar un dato en un árbol
binario ( Otra forma)
int buscarDato(nodoA *A, int dato)
{
if (A)
{
return (A->dato==dato) || buscarDato(A->izq,dato) ||
buscarDato(A->der,dato);
}
else
return 0;
}
Codificar:
Calcular cantidad de nodos de grado 1 en un árbol binario
Árbol binario de búsqueda (ABB)
Árbol binario de búsqueda (ABB)
La solución a nuestro problema de búsqueda es almacenar la colección de
datos a buscar usando un árbol binario de una manera que buscar por un dato en
particular lleve el mínimo esfuerzo. Esta idea es simple:
Por cada nodo del árbol, queremos que el valor de ese nodo nos diga si
encontramos el item, o en que rama debemos continuar para buscar.
 ABB: Características
Un árbol binario de búsqueda (ABB) es un árbol
que está vacío o satisface las siguientes
condiciones:
● Cada nodo tiene una clave asociada.
● Todas las claves que se encuentran en el
subárbol izquierdo son menores que la
raíz.
● Todas las claves que se encuentran en el
subárbol derecho son mayores que la raíz.
● Tanto el subárbol izquierdo como el
derecho son también árboles binarios de
búsqueda.
● No admite claves duplicadas, dado un ABB
y una clave, su ubicación es única.
Inserción en un ABB
Cuando construimos un ABB, uno naturalmente empieza por la raíz y luego agrega
nuevos nodos cuantos sean necesarios. Entonces, para insertar un nuevo valor
“v”, los siguientes casos aparecen:
● Si el árbol está vacío, simplemente se crea el nuevo nodo con el valor v en la
raíz, y dejamos los punteros al subárbol derecho e izquierdo vacíos (NULL).
● Si el árbol no está vacío, entonces se inserta un nodo con el valor v como
sigue:
○ Si “v” es menor al valor de la raíz, se inserta v en el subárbol izquierdo
○ Si “v” es mayor al valor de la raíz, se inserta en el subárbol derecho.
○ Si “v” es igual al valor de la raíz, se viola la regla de la NO inserción de
claves repetidas.
Ejemplo:
Insertar el valor 16, 8 en el siguiente ABB
Codificación
Inserción en ABB
Funciones basadas en el orden en ABB
Una razón importante por la cual los ABB son usados es por que nos permiten
mantener las claves en orden.

● Búsqueda: Suponga que buscamos la clave k. Si la clave que se encuentra en la

raíz no es k, debemos seguir buscando. Si es mayor a la clave k, iremos a buscar
hacia el subárbol izquierdo, de lo contrario, lo haremos sobre el derecho. Este
paso se repite recursivamente, hasta encontrar en el recorrido la clave k.
● Búsqueda Minimo o máximo: Si el subárbol izquierdo de la raíz es NULL, la clave
más pequeña en un ABB es la raíz. Si el subárbol izquierdo no es NULL, la clave
más pequeña en un ABB es la clave más pequeña(mínima) encontrada en el
subárbol izquierdo. Encontrar la máxima clave es similar, moviéndonos hacia el
lado derecho en vez de al izquierdo.
Eliminación en ABB
Eliminación de un nodo de grado 1 u hoja(caso simple)

● Pensemos primero en como eliminar un valor mínimo:

Para eliminar el mínimo, vamos hacia la rama izquierda desde la raíz hasta
encontrar un nodo que tiene su puntero a izq NULL, luego reemplazamos ese
nodo con el valor de su puntero a derecha. Esto ocurre análogamente para la
eliminación del máximo.

● Para eliminar un nodo que es hoja o tiene solamente un hijo, procedemos de

manera análoga al procedimiento de eliminar máximo o mínimo.
 ¿Qué podemos hacer cuando debemos eliminar un nodo
que tiene 2 hijos? (CASO COMPLEJO)
● El nodo tiene dos enlaces, pero tenemos un lugar para reemplazar por sólo uno de
ellos. Una respuesta a este dilema, es eliminar ese nodo x reemplazando su lugar
por su sucesor. Y, como x tiene un hijo a derecha, su sucesor es el nodo con la
clave más pequeña (mínima) en el subárbol derecho. El reemplazo preserva el
orden en el árbol por que no hay claves entre x y el sucesor.
● De forma análoga podemos hacer para reemplazar x pero con el más grande
(máximo) del subárbol izquierdo de x.
Eliminar las claves 7, 15 , del siguiente ABB:
 Proceso de eliminación
Alcanzamos la tarea reemplazando el nodo a borrar X por su sucesor en los siguientes pasos:
● Guardar un puntero al nodo a ser eliminado en algún aux.
● Hacer que aux tenga la clave de su sucesor:
● si aux no posee nodo a izquierda o derecha, el arbol A se volverá esa rama siguiente.
● Si aux posee rama a derecha como a izquierda, se procederá:
○ borrarNodo (función que trabajará con el nodo minimo, enviandole la rama derecha por
referencia del arbol, y el nodo a eliminar).
○ Dentro de la función, recursivamente iremos hacia la izquierda hasta que (*a)->izq sea
null y estemos situados en el nodo más pequeño
○ Una vez situados, asignaremos a la clave del nodo a eliminar, la clave de ese nodo
minimo.
○ Usaremos un aux para guardar ese nodo minimo( que es el que eliminaremos)
○ (*A) = (*A)->der (ya que no queremos perder los enlaces a derecha de ese nodo minimo)
○ Ahora eliminaremos aux (free(aux))
Código...
Función borrar Nodo más a izquierda