ARBOLES
Ing. Rudy Luis Manzaneda Veizaga
Árboles
Un árbol es una estructura no lineal en la que cada
nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un
árbol es una estructura compuesta por un dato y
varios árboles.
Árboles
Recursión
Alguna vez hemos visto ese conjunto de muñecos de madera de origen ruso (matrioshkas) en la que
uno se encuentra dentro de otro.
Dentro del primer muñeco, se encuentra un muñeco menor, y dentro de ese muñeco, hay otro
muñeco de menor tamaño y así sucesivamente.
Un método recursivo es como los muñecos rusos: se reproducen a sí mismo con versiones más y más
pequeñas.
Introducción
Recorrido
un árbol representa una jerarquía
Características
Orden:
Es el numero potencial de hijos que puede tener cada elemento del árbol
Grado:
Es el numero de hijos que tiene el elemento con mas hijos dentro del árbol
Nivel:
se define para cada elemento del árbol como la distancia a la raíz, medida en nodos.
Altura:
la altura de un árbol se define como el nivel del nodo de mayor nivel.
Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol,
también podemos hablar de altura de ramas.
Árboles Binarios
Un árbol binario, requiere de una estructura de NODO que permita almacenar el
dato correspondiente.
además de una referencia al hijo izquierdo y una más al hijo derecho.
El árbol será una liga al nodo raíz, a partir del cual, se podrá acceder al resto de la
estructura.
ARBOLES BINARIOS A
B C
Tipo especial de árbol
Cada nodo no puede tener mas de dos hijos D
Un árbol puede ser un conjunto
Vacío, no tiene ningún nodo RAIZ
O constar de tres partes: A
Un nodo raíz y B C
Dos subárboles binarios: izquierdo y
derecho D E F G
La definición de un árbol binario es H I J
recursiva
Sub. Izq. Sub. Der.
La definición global depende de si misma
• A es el nodo raíz
• B es el padre de D y E
• C es el primo de B
• D y E son los hijos de B
• D, E, F, G, I son nodos externos o
hojas
• A, B, C, H son nodos internos
• La profundidad (nivel) de E es 2
• La altura del árbol es 3
• El grado del nodo B es 2
• Propiedad: (#aristas) = (#nodos) - 1
Representación de los Árboles Binarios
en Memoria
Representación de los Árboles Binarios
en Memoria
Algoritmo de Recorrido
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los
punteros (referencias), del mismo modo en que nos movíamos a través de las listas.
Los recorridos dependen en gran medida del tipo y propósito del árbol
Existen 3 formas de recorrer un árbol completo
Se usa la recursividad
Algoritmo de Recorrido (Preorden)
Si seguimos el árbol del ejemplo en pre-orden, y el
proceso de los datos es sencillamente mostrarlos por
pantalla, obtendremos algo así:
recorrido preorden
Algoritmo preOrder(v)
“visitar” nodo v
for each hijo w de v do
realizar recursivamente preOrder(w)
Ejm: lectura de un documento desde el inicio hasta el final
26
Algoritmo de Recorrido (Inorden)
En este tipo de recorrido, el valor del nodo se
procesa después de recorrer la primera rama y
antes de recorrer la última.
Esto tiene más sentido en el caso de árboles
binarios, y también cuando existen ORDEN-1
datos, en cuyo caso procesaremos cada dato
entre el recorrido de cada dos ramas (este es el
caso de los árboles-b):
recorrido inorder de un árbol binario
Algoritmo inOrder(v)
realizar recursivamente inOrder(leftChild(v))
“visitar” nodo v
realizar recursivamente inOrder(rightChild(v))
• impresión de una expresión aritmética
especialización de un recorrido
inorder
print “(“ antes de recorrer el subárbol
izquierdo
print “)” antes de recorrer el subárbol
derecho
28
Algoritmo de Recorrido (Postorden)
recorrido postorder
Algoritmo postOrder(v)
for each hijo w de v do
realizar recursivamente postOrder(w)
“visitar” nodo v
30
Nodo Cabecera y Hojas
Un árbol binario: conjunto de nodos
typedef struct NodoAB{
Solo se necesita conocer el nodo raíz= nodo cabecera Generico G;
NodoAB *izq, *der;
Cada nodo }NodoAB;
Tiene Contenido y
typedef struct NodoAB *AB;
Dos enlaces: árbol hijo izquierdo, árbol hijo derecho
Un nodo hoja, es aquel cuyos dos enlaces apunta a null
Un nodo en un árbol tiene mas punteros a null que un nodo de
una lista
De un árbol solo se necesita conocer su raíz
La raíz, que es un nodo, puede definir al árbol o
Árboles Binarios de Búsqueda
Árbol ordenado: el hijo de cada nodo está ordenado
Árbol binario: árbol ordenado con todos los nodos internos de grado 2
Definición recursiva de árbol binario:
Un árbol binario es:
- un nodo externo (hoja) o
- un nodo interno (la raíz)
-dos árboles binarios (subárbol izquierdo y subárbol derecho)
Operaciones en ABB
Buscar un elemento
Insertar un elemento
Eliminar un elemento
Movimientos a través del árbol (IZQ, DER, RAIZ)
Información
❑ Verificar si el árbol esta vacio
❑ Numero de Nodos
❑ Comprobar si el nodo es hoja
❑ Calcular el nivel del Nodo
❑ Calcular la altura del Arbol
Búsqueda en Árboles Binarios
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 el valor 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
BUSQUEDA DE UN NODO
Dada una clave, devolver el nodo que la contiene Buscar(raiz,25)
Buscar(raiz,5)
Se comienza en la raiz
Si el arbol esta vacio
No se encontro 8
Si clave buscada es igual a la clave del nodo evaluado
BINGO, LO ENCONTRE
3 20
Si no 1 5 10
Si la clave buscada es mayor a la del nodo evaluado
4 No existe
Buscar en el subarbol derecho
Si no
Buscar en el subarbol izquierdo
Insertar un elemento en Árboles
Binarios
Para insertar un elemento 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.
INSERCION DE UN NODO
Muy parecido a la busqueda Insertar(raiz,15)
Debo insertar en la posicion correcta 15>8…der
15<20…izq
El arbol debe mantener sus propiedades 8
Pasos: 3
15>10
…der 20
Crear una nueva hoja 1 5 10 Insertar
aqui
Buscar en el arbol donde ponerla 4
15
Enlazar el nuevo nodo al arbol
Eliminación
Se trata de un nodo hoja: en ese caso lo borraremos directamente.
Se trata de un nodo rama: en ese caso no podemos 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.
ELIMINACION DE UN NODO
Es mas compleja que la insercion Eliminar(raiz,34)
Al sacar un nodo del arbol
El arbol debe mantener sus propiedades 34
28
El arbol debe reajustarse
18 90
Pasos:
Buscar el nodo p que se va a eliminar 6 25 100
Si el nodo a eliminar tiene menos de dos hijos
20 28
Subir el nodo hijo a la pos. del nodo eliminado
Si no nmayor
Ubicar el nodo q con la mayor de las claves menores
Reemplazar contenido de p con el del nodo q
Eliminar el nodo q que se encontro el el primer paso
Otras Operaciones
Comprobar su un árbol esta vacío
ARBOL A raíz= null;
Calcular el numero de nodos
Contador de los nodos que se están insertando
Hacer el algoritmo de Recorrido
Comprobar si el nodo es hoja
Si no existen hojas dentro de un nodo y es el ultimo es una hoja
Calcular el nivel de un nodo
Calcular el novel del nodo, cada vez que se incremente aumentara su valor
