Árboles...Árboles definición • un árbol es una estructura de datos, que puede definirse de...
TRANSCRIPT
Árboles
Estructura de Datos y Algoritmos
Mag. Ing. Nancy López
Ejemplos de estructuras arborescentes
• Arborescente -con forma de árbol
Ejemplos de estructuras arborescentes
Árboles• Estructura jerárquica.• Se usan habitualmente para organizar
información en sistemas de bases de datos.
Director
SubDir1 SubDir2 SubDir3
J´Dpto1 J´Dpto2 J´Dpto3 J´Dpto4 J´Dpto5
Árboles
Definición• Un árbol es una colección de elementos
llamados nodos, uno de los cuales es distinguido y llamado raíz junto con una relación ser padre que impone una estructura jerárquica en los nodos.
• Un nodo es un árbol= el nodo raíz.
ÁrbolesDefinición• Un árbol es una estructura de datos, que
puede definirse de forma recursiva como:– Una estructura vacía o– Un elemento o clave de información (nodo) más
un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.
Árboles
Definición• Es un grafo acíclico, conexo y no dirigido.• Ejemplo de árbol 2-ario o binario.
Árboles - nomenclatura• Raíz: es aquel elemento que no tiene antecesor;
ejemplo: a. • Rama: arista entre dos nodos. • Antecesor: un nodo X es antecesor de un nodo Y si
por alguna de las ramas de X se puede llegar a Y.• Sucesor: un nodo X es sucesor de un nodo Y si por
alguna de las ramas de Y se puede llegar a X.• Grado de un nodo: el número de descendientes
directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
Árboles - nomenclatura• Hoja: nodo que no tiene descendientes: grado 0.
Ejemplo: d• Nodo interno: aquel que tiene al menos un
descendiente.• Nivel: número de ramas que hay que recorrer para
llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (convención), el nivel del nodo e es 3.
• Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
• Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.
Árbol Binario de Búsqueda
• Un árbol binario es un árbol vacío o un árbol en el cual cada nodo tiene ninguno, uno o dos hijos.
• Llamamos a los hijos hijo izquierdo e hijo derecho.
• La propiedad que hace de un árbol binario un árbol binario de búsqueda es que para todo nodo en el árbol los valores de los nodos en el subárbol izquierdo son menores y los valores de los nodos en el subárbol derecho son mayores.
A
D E F G
CB
A
D E F G
CB
Árbol Binario de BúsquedaRaíz: A.
Rama:
Antecesor: B es antecesor de E.
Sucesor: E sucesor de B.
Grado de un nodo: 2
Hojas: D, E, F, G.
Nodos internos: a, b, c.
Nivel: de A: 1, de B: 2, de D: 3.
Altura: 3.
Anchura: 4.
Árbol Binario de Búsqueda
• Los hijos se ordenan de izquierda a derecha.• Regla de construcción:
– Primero el nodo raíz.– Si el nuevo elemento es menor, se coloca a la
izquierda; si es mayor, a la derecha.
– Ejemplo: 10-5-12-4-7-3-6-9-8-11-14-13-2-1-15-17-18-16
10
5 12
4 7 11 14
3 6 9 13 15
2 8 17
1 16 18
Preorden: 10-5-4-3-2-1-7-6-9-8-12-11-14-13-15-17-16-18
Postorden: 1-2-3-4-6-8-9-7-5-11-13-16-18-17-15-14-12-10
Inorden: 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18
Recorrido• Preorden
– Visita al padre– Preorden hijo izquierdo– Preorden hijo derecho
* Visita es cualquier operación sobre el nodo, por ejemplo, mostrarNodo.
Árbol Binario de Búsqueda
Recorrido• Inorden
– Inorden hijo izquierdo– Visita al padre– Inorden hijo derecho
* Visita es cualquier operación sobre el nodo, por ejemplo, mostrarNodo.
Árbol Binario de Búsqueda
Recorrido• Postorden
– Postorden hijo izquierdo– Postorden hijo derecho– Visita al padre
* Visita es cualquier operación sobre el nodo, por ejemplo, mostrarNodo.
Árbol Binario de Búsqueda
Árbol Binario de Búsqueda
• Definiciónstruct nodoArbol
{int valor;int cant;nodoArbol *izq;nodoArbol *der;
};typedef nodoArbol *ABB;
Árbol Binario de Búsqueda
• Crear un nuevo nodo
ABB crearNodo(int v){
ABBnuevo=new nodoArbol;nuevo->valor=v;nuevo->izq=NULL;nuevo->der=NULL;return nuevo;
}
Árbol Binario de Búsqueda• Insertar un nodo
void insertar (ABB &arbol, ABB v){if (arbol==NULL)
arbol=v;elseif(v->valor<arbol->valor)insertar(arbol->izq,v);
elseif(v->valor>arbol->valor)insertar(arbol->der, v);
}
Árbol Binario de Búsqueda
• Mostrar en preorden
void preOrden(ABB arbol){if (arbol==NULL)
return;cout<<arbol->valor<<" ";preOrden(arbol->izq);preOrden(arbol->der);}
Árbol Binario de Búsqueda
• Recorrido en postorden
void postOrden(ABB arbol){if (arbol==NULL)
return;postOrden(arbol->izq);postOrden(arbol->der);cout<<arbol->valor<<" ";}
Árbol Binario de Búsqueda
• Recorrido en inorden
void inOrden(ABB arbol){if (arbol==NULL)
return;inOrden(arbol->izq);cout<<arbol->valor<<" ";inOrden(arbol->der);}
Borrar un nodo• Si no está, no se elimina.• Si el nodo es una hoja, se elimina
directamente.• Se toma el hijo derecho del Nodo que
queremos eliminar y se recorre hasta el hijo más a la izquierda (o viceversa), se intercambia el valor del nodo que se quiere eliminar por el nodo que encontrado, luego se elimina el nodo.
Árbol Binario de Búsqueda• Borrar un nodo
void borrar(ABB &arbol, int x){
if(arbol==NULL) return;
if(x<arbol->valor)borrar(arbol->izq, x);
elseif(x>arbol->valor)
borrar(arbol->der, x);else{
ABB p = arbol;arbol = unirABB(arbol->izq, arbol->der);delete p;
}}
Árbol Binario de BúsquedaABB unirABB(ABB izq, ABB der){
if(izq==NULL) return der;if(der==NULL) return izq;
ABB centro = unirABB(izq->der, der->izq);izq->der = centro;der->izq = izq;return der;
}