arboles
TRANSCRIPT
Universidad Fermín Toro
Escuela de Computación
Estructuras de Datos I
José Miguel Torres M 19.106.680
Luis Miguel Henríquez S 20.913.021
ARBOLES
¿Qué es un Árbol?
Un árbol es una estructura jerárquica no lineal que posee un número de
elementos finitos llamados nodos, posee una relación padre – hijo entre sus
nodos.
Se puede representar un árbol como el organigrama de una empresa. Poniendo
como raíz al presidente y desprendiendo de ahí los nodos padres, hijos y hojas del
mismo.
Forma de representar un Árbol
MiEmpresa
Ventas Producción
Portátiles Pc’s Ve Internacional
Europa Asia América
Características de un Árbol
Un árbol se caracteriza por estar formado por una serie de nodos conectados por
una serie de aristas que verifican que:
1. hay un único nodo raíz.
2. cada nodo, excepto la raíz, tiene un único padre.
3. hay un único camino (desde la raíz hasta cada nodo).
Nodo: Cada elemento del árbol.
Nodo RAIZ: El primer elemento del árbol no posee antecesores.
A
B C
D E F G
I H
Nodo RAIZ
Nodo Padre: es el nodo predecesor de 1 o más nodos.
Nodo Hijo: Es el nodo sucesor de un elemento.
Hermanos: Son los nodos predecesores del mismo padre.
Nodo interno: Tiene al menos un hijo.
Nodo Hojas: No tiene hijos.
A
B C
D E F G
H
C: es padre de F y G
F y G son Hijos de C
F y G son hermanos
A
B C
D E F G
H
D: Es un nodo interno
H: es un nodo hoja
Subárbol: Son todos los nodos descendientes por la izquierda o derecha de un
padre.
Nivel:Es el largo del camino de la raíz al nodo. Cada vez que un nodo se ramifica
aumenta el nivel.
A
B C
D E
F G
H
Subárbol Izquierdo de B
Subárbol derecho de B
A
B C
D E F
G
H
Nivel 0
Nivel 1
Nivel 2
Nivel 3
Grado: Es el número de descendientes directos de un nodo. El grado máximo de
todos los nodos es el grado del árbol.
Altura: Son las capas que crecen a partir de la raíz. La altura de un árbol es la
altura de la raíz.
B C
D E
F G H
I J K
A
A
B C
D E F G H
I J K
Árbol Binario
Los árboles binarios son los que tienen a lo más dos hijos por cada nodo. Un árbol
binario completo o balanceado es aquel en el cual todos los nodos tienen dos
hijos, salvo los que están en el último nivel.
Arboles binarios distintos: Se dice que dos árboles binarios son distintos cuando
sus estructuras son diferentes.
A
B C
D E F G
H I
A
B C
D E F G
H I
Árbol Binario Similar
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la
información que contienen sus nodos es diferente.
A
B C
D E F G
H I J K
A
B C
D E F G
H I
Árbol Binario Equivalente
Son aquellos árboles que son similares y que además los nodos contienen la
misma información:
A
C B
D E F G
H I
A
C B
D E F G
H I
A
C B
D E F G
H I
Representación mediante arreglos:
Cuando se tiene los nodos etiquetados con enteros, es posible usar una
representación mediante arreglos unidimensionales A, en donde el índice i
representa el valor del nodo i, y A(i) representa el valor del padre de i
A(i) es el nodo padre del nodo i
A(4)=B es el nodo padre del nodo D
0 1 1 2 2 5 5 5 3 3
1 2 3 4 5 6 7 8 9 10
Representación en memoria dinámica: Los árboles se pueden representar en
memoria estática a través de estructuras arreglo. También se puede hacer a
través de estructuras dinámicas. Su representación es la siguiente:
Ejemplo: Representar la expresión (A*B)+(C/D)^ 35
+
* ^
A B / 35
C D
Recorrer un árbol en preorden:
Se debe comenzar por el nodo raíz.
Recorrer el subárbol izquierdo en preorden.
recorrer el subárbol derecho en preorden.
Pseudo código para hacer el recorrido en preorden
Preorden
Comience
si (t <> 0)entonces
Imprima info (*t)
preorden (Ni(*t))
preorden (Nd(*t))
Sino
fin-si
Termine
RECORRIDO: A, B, D, C, E, G, H, F
Recorrido de un árbol en postorden:
Recorrer el subárbol izquierdo en postorden.
Recorrer el subárbol derecho en postorden.
Examinar la raíz.
Si(t<> 0) ejecute
posorden(ei(*t))
posorden (ed(*t))
imprima info (*t)
Sino
fin-si
Termine
RECORRIDO: D, B, G, H, E, F, C, A.
Recorrido de un árbol en inorden:
Recorrer el subárbol izquierdo en inorden.
Examinar la raíz.
Recorrer el subárbol derecho en inorden.
Pseudocodigo del recorrico inorden
si (t <> ) entonces
inorden (Ni(*t))
imprima info (*t)
inorden (Nd(*t))
Sino
fin-si
Termine
RECORRIDO: D, B, A, G, E, H, C, F.
Códigos en lenguaje c para crear, insertar un nodo y eliminar un nodo en un árbol. En memoria Dinamica
TYPE
TipoPuntero = ^TipoNodoABB;
TipoNodoABB = RECORD
info : TipoInfo;
izquierdo : TipoPuntero;
derecho: TipoPuntero;
End;
Crear un ABB vacío.
Procedure InicializaArbol(var RaizArbol: TipoPuntero);
Begin
RaizArbol := NIL;
Insertar nuevos elementos al ABB.
Procedure Insertar_arbol_binario( var Raizarbol: TipoPuntero;InfoNodo: TipoInfo);
Var
NuevoNodo: TipoPuntero; (*puntero para nodo nuevo*)
Ptr, Anterior:TipoPuntero; (* usado para buscar en el ABB*)
ClaveNueva: TipoClave;(* clave del nuevo nodo a insertar*)
BEGIN
(* Crear un nuevo nodo*)
New(NuevoNodo); NuevoNodo^.izquierdo:= NIL; NuevoNodo^.derecho:= NIL;
NuevoNodo^.info:= InfoNodo;
(* Buscar el lugar de inserción*)
ptr: = RaizArbol; Anterior: = NIL;
While ptr <> NIL Do
begin
anterior : = ptr;
if ptr^.info.clave > ClaveNueva then
ptr := ptr^.izquierdo
else
ptr := ptr^.derecho
end;
if anterior = NIL then
raizarbol = NuevoNodo
else
if anterior^.info.clave > ClaveNueva then
anterior^.izquierdo: = Nuevonodo
else
anterior^.derecho: = Nuevonodo
END;
Eliminar elementos ya existentes.
(a)Eliminación de un nodo hoja sólo consiste en anular el puntero de su nodo padre
(b)Eliminación de un nodo con un hijo, es necesario reasignar el puntero del padre hacia el hijo.
(c)Eliminación de un nodo con dos hijos : Reemplazar el nodo que deseamos suprimir con el nodo de valor más próximo al
valor del nodo suprimido. Así será posible hacer el reemplazo por "El mayor más cercano" o "El menor más cercano",
dependiendo de qué subárbol sea escogido el nodo.
Procedure Suprimir (Var RaizArbol: TipoPuntero;ValorClave: TipoClave);
(* Suprime el valor que contiene ValorClave del árbol, apuntado por RaizArbol, supondremos que este nodo existe en el
árbol*)
Var
ptr, anterior: TipoPuntero;
BEGIN
ptr := RaizArbol; anterior:= NIL;
While ptr ^.info.clave<> ValorClave Do
begin
anterior : = ptr;
if ptr^.info.clave > ValorClave then
ptr := ptr^.izquierdo
else
ptr := ptr^.derecho
end;
(* Suprimir nodo apuntado por ptr*, anterior apunta al padre de este nodo*)
SuprimirNodo(RaízArbol, ptr, Anterior)
END;
Procedure SuprimirNodo (Var RaízArbol : Tipo_Puntero; ptr, anterior: Tipo_ Puntero);
(* Suprime el nodo apuntado por Ptr sobre el árbol binario con puntero RaizArbol, Anterior es un puntero al nodo
padre ( NIL si el nodo a suprimir es el nodo Raiz)*)
Var
temp: Tipo_Puntero;
BEGIN
(*Caso b.1 Supresión de una hoja*)
if(ptr^.derecho = NIL) AND (ptr^.izquierdo = NIL) then
IF Anterior = NIL then (*Nodo(ptr) es el último en el árbol)
RaizArbol:= NIL
else
if anterior^.derecho = Ptr then
anterior^.derecho : = NIL
else anterior^.izquierdo: = NIL
else (* Caso b.3 supresión de nodo con dos hijos*)
if(ptr^.derecho <> NIL) AND (ptr^.izquierdo <> NIL) then
begin (* Encontrar el valor para reemplazar, valor más próximo al eliminado*)
anterior: = ptr;
temp := ptr^.izquierdo;
While temp^.derecho<> NIL Do
begin
anterior:= temp;
temp : = temp^.derecho
end;
(* Copiar la información a reemplazar en el nodo*)
ptr^.info:= temp^.info;
if anterior = Ptr then
anterior^.izquierdo:= temp^.izquierdo
else
anterior^.derecho:= temp^.izquierdo;
ptr:= temp;
end
else (* Caso b.2 Nodo con un hijo*)
(* Inicializa uno de los campos punteros de nodo (anterior) dependiendo si el nodo que se está suprimiendo tiene
un hijo a la derecha o izquierda*)
if ptr^.derecho <>NIL then (* Hay un hijo derecho*)
if anterior = NIL then
RaizArbol:= Ptr^.derecho
else
if anterior^.derecho=ptr then
anterior^.derecho := ptr^.derecho
else
anterior^.izquierdo := ptr^.derecho
else(* hay un hijo izquierdo*)
if anterior = NIL then
RaizArbol:= Ptr^.izquierdo
else
if anterior^.derecho=ptr then
anterior^.derecho := ptr^.izquierdo
else
anterior^.izquierdo := ptr^.izquierdo;
dispose (ptr);
END;