Download to get the file

Tema 4 Árboles.
Conceptos Generales.
Definición
 Estructura de datos jerárquica
(no lineal) que puede
representarse como un conjunto
de nodos enlazados entre sí por
medio de ramas.
 Formalmente, un árbol es una
estructura da datos que cumple
una de las siguientes
condiciones:
 Estructura vacía
 Nodo de tipo base que tiene de 0 a
Nodo base: raíz del árbol
1
7
4
5
3
9
17
N subárboles disjuntos entre sí.
29
44
69
Conceptos (I):
 Nivel de un nodo: número de
Nivel 1
nodos a recorrer hasta llegar a
él
 Nivel de la raíz = 1
 Profundidad de un nodo:
Nivel 2
1
7
3
5
número de predecesores más
1
 Profundidad (1) = 1
Nivel 3
4
9
17
 Profundidad (9) = 3
 Altura del árbol: profundidad
máxima.
 Altura = 4
Nivel 4
29
44
69
Conceptos (II):
 Camino del nodo X al nodo Y: sucesión de
nodos que permitan llegar desde X a Y.
 Antecesor: A es un nodo antecesor de B si para
alcanzar B, desde el nodo raíz, es necesario pasar
por A.
 Sucesor: B es un nodo sucesor de A, si A es
antecesor de B.
 Raíz: único nodo que no tiene antecesor
 Nodo hoja: nodo sin sucesores
 Subárbol: árbol formado por un nodo y sus
descendientes
 Grado de un nodo: número de hijos
 Grado del árbol: el mayor de los grados de los
nodos
 Amplitud/anchura del árbol: número de
nodos del nivel más poblado.
1
7
4
3
9
29
5
17
44
69
Árbol completo
 Todos los nodos (excepto las hojas) tienen el mismo grado y los
diferentes niveles están poblados por completo
 Para obtener un árbol completo se pueden generar nodos especiales
 En un árbol completo:
 Amplitud del nivel n: An = gn-1
 Número de nodos: Nn =
gn -1
g -1
1
7
4
3
9
17
5
Definición.
 Árbol de grado 2
 Implementación física:
 Estructura estática (matrices)
 Estructura dinámica
 Los nodos de un árbol tienen (al menos) tres
componentes:
 Clave (de tipo simple o estructurada)
 Puntero que indique la ubicación del árbol derecho
 Puntero que indique la ubicación del árbol izquierdo
Además: convención para indicar que no tiene hijos (valor null)
1
0
7
4
3
9
1
2
3
4
5
clave 1 7
3
4
9
17
Ar.Iz
1 3
5
*
*
*
Ar.De 2 4
*
*
*
*
17
Memoria estática
arbol
Memoria dinámica
NodoArbol
1
nombre
*
raiz
3
7
17
Arbol
4
*
*
9
*
*
*
*
Definición de las clases
 Clase Arbol
public class Arbol {
String nombre;
NodoArbol raiz;
 Clase NodoArbol
public class NodoArbol {
int clave;
NodoArbol iz;
NodoArbol de;
public Arbol () {
nombre = null;
raiz = null;
}
public NodoArbol () {
clave = 0;
iz = null;
de = null;
}
}
}
Árboles binarios de búsqueda (I).
 Concepto:
 Un árbol binario de búsqueda (ABB) es un árbol
binario en el que se verifica que las claves del
subárbol izquierdo son menores que las claves
del árbol derecho.
 Características:
 Mayor eficiencia en búsquedas.
 Listado de claves ordenadas: orden central.
Árboles binarios de búsqueda (II)
Ejemplo