Download Raíz

Tema 3 Árboles.
Conceptos Generales.
Curso 2014/2015
ETSISI UPM
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
Arbol
Memoria estática
raiz
Memoria dinámica
NodoArbol
1
3
*
7
17
4
*
*
9
*
*
*
*
Definición de las clases
 Clase NodoArbol
NodoArbol.h
 Clase Arbol
Arbol.cpp
#include <iostream>
#ifndef NODOARBOL_H_
#define NODOARBOL_H_
class NodoArbol {
public:
int clave;
NodoArbol *iz, *de;
NodoArbol() {
clave = 0;
iz = de = NULL;
}
#endif /* NODOARBOL_H_ */
#include "NodoArbol.h"
#ifndef ARBOL_H_
#define ARBOL_H_
typedef NodoArbol *pNodoArbol;
class Arbol {
public:
//Variables miembro
pNodoArbol raiz;
//interfaz
Arbol ();
Arbol (int dato);
Arbol.h
~Arbol ();
};
• Clase Arbol
#include "Arbol.h"
Arbol::Arbol (){
raiz = NULL;
}
Arbol::Arbol (int dato){
raiz = new NodoArbol (dato);
}
void destruir (pNodoArbol &nodo) {
if (nodo != NULL) {
destruir (nodo->iz);
destruir (nodo->de);
delete nodo;
nodo = NULL;
}
}
Arbol::~Arbol () {
pNodoArbol nodo = raiz;
destruir (nodo);
raiz = 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