Árboles...Árboles definición • un árbol es una estructura de datos, que puede definirse de...

Á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;

}