Download to get the file
Document related concepts
no text concepts found
Transcript
Tema 4 Árboles. Árboles binarios. Algoritmos básicos Algoritmos básicos con árboles binarios Recorrido completo. Creación. Terminación anticipada. Recorridos especiales. Manejo de varias estructuras. Recorrido en Preorden. // Escribe las claves del árbol binario en preorden. static void preOrden (NodoArbol arbol) { if (arbol != null) { System.out.print (arbol.clave+" ") ; arbol preOrden (arbol.iz); preOrden (arbol.de); } } public void preorden () { preorden (raiz); } nombre raiz Aplicado a objetos de la clase Arbol: 1 2 Orden de visita de nodos: 3 1, 2, 4, 9, 15, 5, 3, 8 y 7. 4 Preferido para: Búsquedas. 9 5 15 8 7 Recorrido en Orden Central Aplicado a objetos de la clase Arbol: nombre // Escribe las claves del árbol binario en orden central. static void ordenCentral (NodoArbol arbol) { if (arbol != null) { ordenCentral (arbol.iz); System.out.print (arbol.clave+" "); ordenCentral (arbol.de); } } public void ordenCentral () { ordenCentral (raiz); 4 } Orden de visita de nodos: 9, 4, 15, 2, 5, 1, 8, 3 y 7. 9 raiz arbol 1 2 3 5 8 15 Preferido para: Recorrido de acuerdo al orden físico de los nodos. En árboles binarios de búsqueda recupera la secuencia. 7 Recorrido en Postorden // Escribe las claves del árbol binario en postorden. static void postOrden (NodoArbol arbol) { arbol if (arbol != null) { postOrden (arbol.iz); postOrden (arbol.de); System.out.print (arbol.clave + " ") ; } } public void postOrden () { postOrden (raiz); } Orden de visita de nodos: 1 2 4 9, 15, 4, 5, 2, 8, 7, 3 y 1. Preferido para: Liberar memoria. Nodos buscados en los niveles más bajos del árbol. nombre 9 raiz Aplicado a objetos de la clase Arbol: 3 5 15 8 7 Ejemplo: suma de claves static int sumaClaves (NodoArbol nodoArbol) { int resul = 0; if (nodoArbol != null) { resul = nodoArbol.clave + sumaClaves (nodoArbol.iz); resul = resul + sumaClaves (nodoArbol.de); } return resul; } static int sumaClaves (Arbol a) { return sumaClaves (a.raiz); } If (nodoArbol != null) { resul =sumaClaves(nodoArbol.iz)+nodoArbol.clave; resul =resul+sumaClaves(arbol.de); } 1 else resul=0 34 resul =15+24=39 6 17 resul =9+6 18 16 resul=5+4 = 9 33 resul =15+9=24 25 resul =7+8 9 resul=2+3 3 8 2 10 19 26 2 3 8 resul=2+0 = 2 5 resul=0+2 6 null 4 resul=0 null 7 resul=0 24 resul =7+0 = 7 22 resul =0+7 7 13 resul=0+4 4 11 14 null 12 resul=0 null 15 resul=0 20 null 21 resul=0 null 23 resul=0 32 resul=9+0 = 9 29 resul=0+9 9 30 27 null 28 resul=0 null 31 resul=0 Recorrido en Amplitud arbol static void probarAmplitud (Arbol arbol) { NodoArbol referencia; ColaArbol colaArbol = new ColaArbol (); referencia = arbol.raiz; if (referencia != null) colaArbol.encolar (referencia); while (! colaArbol.colaVacia ()) { referencia = colaArbol.desencolar (); System.out.print (referencia.clave + " "); if (referencia.iz != null) colaArbol.encolar (referencia.iz); if (referencia.de != null) colaArbol.encolar (referencia.de); } raiz Arbol nombre 1 2 } Orden de visita de nodos: 4 5 1, 2, 3, 4, 5, 8, 7, 9 y 15. 9 3 15 8 7 Obtención de la copia de un árbol static Arbol copiarArbol (Arbol arbol) { Arbol resul = new Arbol(); resul.nombre = "Arbol copia"; if (arbol.raiz != null) resul.raiz = copiaArbol (arbol.raiz); return resul; } static NodoArbol copiaArbol (NodoArbol nodoArbol) { NodoArbol nuevoNodo = new NodoArbol(); nuevoNodo.clave = nodoArbol.clave; if (nodoArbol.iz != null) nuevoNodo.iz = copiaArbol (nodoArbol.iz); if (nodoArbol.de != null) nuevoNodo.de = copiaArbol(nodoArbol.de); return nuevoNodo; } Insertar Criterio de inserción: Orden de los nodos. Operación juntar (join). Preguntar en qué rama se quiere insertar … No se permite insertar claves repetidas Búsqueda previa del dato que se quiere insertar para evitar repeticiones. Se inserta cuando alcanzamos el nivel más profundo (nodos hojas) de la rama seleccionada. Inserción en árbol binario genérico static public void juntar (Arbol arbol, int dato, Arbol a1, Arbol a2) { if (a1.raiz == a2.raiz && a1.raiz != null) System.out.println ("no se pueden juntar, a1 y a2 son iguales") ; else { arbol.raiz = new NodoArbol () ; arbol.raiz.clave = dato; arbol.raiz.iz = a1.raiz; arbol.raiz.de = a2.raiz; if (arbol != a1) a1.raiz = null; if (arbol != a2) a2.raiz = null; } } Inserción en árbol binario de búsqueda. static NodoArbol insertar (NodoArbol arbol, int dato) { NodoArbol resul = arbol; if (arbol != null) if (arbol.clave < dato) arbol.de = insertar (arbol.de, dato); else if (arbol.clave > dato) arbol.iz = insertar (arbol.iz, dato); else System.out.println ("la clave ya existe"); else resul = new NodoArbol (dato); return resul; } public void insertar (int dato) { raiz = insertar (raiz, dato); } Método static que recibe un NodoArbol y devuelve otro como resultado Método de objeto de Arbol Búsqueda en árbol binario. boolean encontrar (int dato) { return encuentra (raiz, dato); } static boolean encuentra (NodoArbol nodoArbol, int dato) { boolean resul; if (nodoArbol != null) if (nodoArbol.clave == dato) resul = true; else { resul = encuentra (nodoArbol.iz, dato); if (!resul) resul = encuentra (nodoArbol.de, dato); } else resul = false; return resul; } Búsqueda en árbol binario de búsqueda. boolean encontrar (int dato) { return encuentra (raiz, dato); } public static boolean encuentra (NodoArbol nodoArbol, int dato) { boolean resul = false; if (nodoArbol != null) if (nodoArbol.clave == dato) resul = true; else if (nodoArbol.clave > dato) resul = encuentra (nodoArbol.iz, dato); else resul = encuentra (nodoArbol.de, dato); return resul; } Ejemplo: Verificar que un árbol Binario es de Búsqueda static class arbolBusqueda { static int ant; static boolean primero = true; static boolean esBusqueda (NodoArbol arbol) { boolean resul; if (arbol == null) resul = true; else { resul = esBusqueda (arbol.iz); if (primero) primero = false; else if (arbol.clave <= ant) resul = false; if (resul) { ant = arbol.clave; resul = esBusqueda(arbol.de); } } static boolean esBusqueda (Arbol a) { return resul; return arbolBusqueda.esBusqueda (a.raiz); } } } Eliminar una clave (I). Fase I. Se localiza la clave a eliminar (si existe). Fase II. Tres posibles situaciones: Clave está en un nodo hoja: Liberar memoria (innecesario en Java) y asignar el árbol a null. Clave tiene un único descendiente: Apuntar al subárbol no vacío y liberar memoria (innecesario en Java). Clave tiene dos descendientes: [Orden topológico anterior] Se localiza el descendiente más a la derecha del hijo izquierdo, se sustituye la clave a borrar por la clave encontrada, se “cortocircuita” el subárbol izquierdo y se borra (innecesario en Java) el nodo que contenía la clave sustituida. Eliminar una clave (II). Peculiaridades del lenguaje Java. Causa: Las referencias (punteros) se pasan por valor. Efecto: Los cambios realizados en la instancia actual sobre el puntero (NodoArbol) que se recibe como argumento no surten efecto cuando se retorna a la instancia de llamada. Técnica posible: Construir métodos que devuelvan actualizado el puntero (referencia) que se recibe como argumento. Ejemplo: static NodoArbol elimina (NodoArbol nodoArbol, int dato) { // cuerpo del método que modifica nodoArbol; return nodoArbol; } static void eliminarClave (Arbol arbol, int dato) { arbol.raiz = eliminarElemento (arbol.raiz, dato); } static NodoArbol eliminarElemento (NodoArbol arbol, int elem) { NodoArbol p; if (arbol != null) if (arbol.clave > elem) arbol.iz = eliminarElemento (arbol.iz, elem); else if (arbol.clave < elem) arbol.de = eliminarElemento (arbol.de, elem); else { p = arbol; if (arbol.iz == null) arbol= arbol.de; else if (arbol.de == null) arbol = arbol.iz; else arbol.iz = eliminar2Hijos (arbol.iz, p); } else System.out.println (" la clave buscada no existe"); return arbol; } static NodoArbol eliminar2Hijos (NodoArbol arbol, NodoArbol p) { NodoArbol resul; if (arbol.de != null) { resul = arbol; arbol.de = eliminar2Hijos (arbol.de, p); } else { p.clave = arbol.clave; resul = arbol.iz; } return resul; } Eliminar un árbol. static void eliminarArbol (Arbol arbol) { System.out.println ("NOTA: Este algoritmo es innecesario en Java "); System.out.println (“Lo que no sucede en todos los lenguajes"); if (arbol.raiz == null) System.out.println ("Arbol vacio"); else { arbol.raiz =eliminaArbol (arbol.raiz); System.out.println (“Faltaría 'destruir' la referencia principal (arbol)"); } } static NodoArbol eliminaArbol (NodoArbol nodoArbol) { NodoArbol resul; if (nodoArbol != null) { nodoArbol.iz = eliminaArbol (nodoArbol.iz); nodoArbol.de = eliminaArbol (nodoArbol.de); System.out.println ("Clave antes de ser eliminada: “+nodoArbol.clave); nodoArbol = null; resul = nodoArbol; } else resul = null; return resul; } Tratamiento de hojas. Ejemplo. Condición de hoja: (nodoArbol.iz == null) && (nodoArbol.de == null) Ejemplo: Devuelve el número de hojas de un árbol static int cuentaHojas (Arbol arbol) { return contarHojas (arbol.raiz); } static int contarHojas (NodoArbol nodoArbol) { int resul = 0; if (nodoArbol != null) if ((nodoArbol.iz == null) && (nodoArbol.de == null)) resul = 1; else resul = contarHojas (nodoArbol.iz) + contarHojas (nodoArbol.de); return resul; } Constancia de nivel. Recorrido en profundidad (I) Mecanismo: Se pasa un argumento entero (inicializado a 1) que se incrementa en cada llamada. Ejemplo: static void clavesNiveles (Arbol arbol) { clavesNiveles (arbol.raiz,1); } static void clavesNiveles (NodoArbol nodoArbol, int n) { if (nodoArbol != null) { System.out.println ("Clave: “ + nodoArbol.clave + " en el nivel: “ + n); clavesNiveles (nodoArbol.iz, n+1); clavesNiveles (nodoArbol.de, n+1); } } Constancia de nivel. Recorrido en profundidad (II) Ejemplo: Método que devuelve la altura de un árbol. static int pruebaAltura (Arbol arbol) { int resul = 0; if (arbol.raiz != null) resul = Altura.altura (arbol.raiz,1); return resul; } static int altura (NodoArbol nodoArbol, int n, int altura) { int resulIz, resulDe; if (nodoArbol != null) { if (n > altura) altura = n; resulIz = altura (nodoArbol.iz, n+1, altura); resulDe = altura (nodoArbol.de, n+1, altura); altura = Math.max (resulIz, resulDe); } return altura; } Constancia de nivel. Recorrido en amplitud (I). Dos opciones: Iteración anidada en dos niveles. Modificar la cola de referencias a nodos del árbol para que incluya una variable con el nivel. Constancia de nivel. Recorrido en amplitud (II) Sin modificar la cola de referencias. Dos iteraciones: Externa que recorre el árbol en niveles Interna que visita los nodos en amplitud Variables: contador: controla el recorrido del nivel actual: amplitud del nivel siguiente: número de hijos del siguiente nivel static void ListarAmplitud (Arbol arbol) { Cola c = new tad_cola (); int actual, siguiente, contador, altura; NodoArbol p p = arbol.raiz; Arbol.raiz altura = 0; siguiente = 1; p p = arbol; 2 if (p != null ) c.encolar (p); 4 5 while (!c.colaVacia()) { actual = siguiente; siguiente = 0; ↑1 contador = 1; altura++; altura = 0 while (contador <= actual) { siguiente =1; p = c.desencolar (); System.out.println ("clave: "+p.clave+" nivel: "+altura); contador++; if (p.iz != null) { c.encolar (p.iz); siguiente++; } if (p.de != null) { c.encolar (p.de); siguiente++; } } } } 1 3 8 altura = 0 static void ListarAmplitud (Arbol arbol) { siguiente = 1; Cola c = new tad_cola (); Arbol.raiz int actual, siguiente, contador, altura; c.inicializarCola (); p NodoArbol p = arbol.raiz; 2 altura = 0; siguiente = 1; p = arbol; 4 5 if (p != null ) c.encolar (p); ↑1 while (!c.colaVacia()) { actual = siguiente; actual = 1 siguiente = 0; contador = 1; siguiente = 0 altura++; contador = 0 while (contador <= actual) { altura = 1 p = c.desencolar (); System.out.println ("clave: "+p.clave+" nivel: "+altura); contador++; if (p.iz != null) { c.encolar (p.iz); siguiente++; } if (p.de != null) { c.encolar (p.de); siguiente++; } } } } 1 3 8 Iteración interna: static void ListarAmplitud (Arbol arbol) { NodoArbol p p = arbol.raiz; while (contador <= actual) actual = 1 Cola c = new tad_cola (); contador = 0 int actual, siguiente, contador, altura; altura = 1 Arbol.raiz altura = 0; siguiente = 1; 1 c.inicializarCola (); p p = arbol; 2 3 if (p != null ) c.encolar (p); 4 5 8 while (!c.colaVacia()) { actual = siguiente; ↑2 ↑3 siguiente = 0; contador = 1; altura++; while (contador <= actual) { clave es 1, altura 1 ↑1 p = c.desencolar (); contador = 1 System.out.println ("clave: "+p.clave+" nivel: "+altura); contador++; siguiente = 1 if (p.iz != null) { siguiente = 2 c.encolar (p.iz); siguiente++; } salimos de la iteración interna if (p.de != null) { c.encolar (p.de); siguiente++; } } } } Arbol.raiz static void ListarAmplitud (Arbol arbol) { 1 NodoArbol p p = arbol.raiz; P siguiente =2 Cola c = new tad_cola (); altura =1 2 3 int actual, siguiente, contador, altura; altura = 0; 4 5 8 siguiente = 1; c.inicializarCola (); p = arbol; ↑2 ↑3 if (p != null ) c.encolar (p); actual = 2 while (!c.colaVacia()) { siguiente = 0 actual = siguiente; contador = 0 siguiente = 0; altura = 2 contador = 1; altura++; while (contador <= actual) { while (contador <= actual) p = c.desencolar (); System.out.println ("clave: "+p.clave+" nivel: "+altura); 1 P contador++; if (p.iz != null) { ↑3 ↑4 2 3 ↑5 c.encolar (p.iz); siguiente++; } 4 5 8 if (p.de != null) { c.encolar (p.de); siguiente++; ↑2 siguiente = 1 } siguiente = 2 } clave es 2 y altura 2 } contador = 1 } iteración interna: static void ListarAmplitud (Arbol arbol) { while (contador <= actual) NodoArbol p p = arbol.raiz; 1 P Cola c = new tad_cola (); int actual, siguiente, contador, altura; ↑4 2 3 ↑5 ↑8 altura = 0; siguiente = 1; 4 5 8 c.inicializarCola (); p = arbol; ↑3 if (p != null ) c.encolar (p); siguiente = 3 while (!c.colaVacia()) { clave es 3 y altura 2 actual = siguiente; siguiente = 0; contador = 2 contador = 1; altura++; ---- salimos de la iteración interna ---while (contador <= actual) { p = c.desencolar (); System.out.println ("clave: "+p.clave+" nivel: "+altura); P contador++; 1 if (p.iz != null) { c.encolar (p.iz); ↑4 2 3 ↑5 ↑8 siguiente++; } 4 5 8 if (p.de != null) { c.encolar (p.de); siguiente++; actual = 3 } siguiente = 0 } contador = 0 altura = 3 } } clave es 3 y altura 2 iteración interna: static void ListarAmplitud (Arbol arbol) { while (contador < =actual) NodoArbol p p = arbol.raiz; Cola c = new tad_cola (); 1 P int actual, siguiente, contador, altura; altura = 0; 2 ↑5 ↑8 siguiente = 1; c.inicializarCola (); 4 5 8 p = arbol; ↑4 if (p != null ) actual = 3 c.encolar (p); contador = 1 while (!c.colaVacia()) { actual = siguiente; clave es 4 y altura 3 siguiente = 0; contador = 1; altura++; actual = 3 ↑8 while (contador <= actual) { contador = 2 p = c.desencolar (); ↑5"+altura); System.out.println ("clave: "+p.clave+" nivel: clave es 5 y altura 3 contador++; if (p.iz != null) { c.encolar (p.iz); siguiente++; actual = 3 } contador = 3 if (p.de != null) { c.encolar (p.de); clave es 8 y altura 3 ↑8 siguiente++; } } } } 3 Constancia de nivel. Recorrido en amplitud (III) Modificando la cola de referencias. class tElemento { int nivel; NodoArbol nodoArbol; tElemento (NodoArbol a, int n) { nivel = n; nodoArbol = a; } class NodoColaArbolModificada { NodoColaArbolModificada siguiente; tElemento elem; NodoColaArbolModificada () { elem = null; siguiente = null; } } } public class ColaArbolModificada { private NodoColaArbolModificada principio; private NodoColaArbolModificada fin; public ColaArbolModificada () { principio = null; fin = null; } } Constancia de nivel. Recorrido en amplitud (IV) static void listarAmplitud (Arbol arbol) { NodoArbol p; int nivel; ColaArbolModificada cola = new ColaArbolModificada(); p = arbol.raiz; if (p != null) { tElemento elem = new tElemento (referencia, 1); cola.encolar(elem); while (! cola.colaVacia()) { elem = cola.desencolar (); p = elem.nodoArbol; nivel = elem.nivel; System.out.println("nivel: "+nivel+" "+p.clave+" "); if (p.iz != null) { elem = new tElemento(p.iz,nivel+1); cola.encolar(elem); } if (p.de != null) { elem = new tElemento (p.de, nivel+1); cola.encolar(elem); } } } } Ver codigo nodoArbol 1 p static void listarAmplitud(Arbol arbol) { 2 NodoArbol referencia; int nivel; 4 5 ColaArbolModificada cola = new ColaArbolModificada(); p = arbol.raiz; ↑1 1 if (p != null) { tElemento elem = new tElemento (p, 1); cola.encolar(elem); nodoArbol while (! cola.colaVacia()) { elem = cola.desencolar(); p = elem.nodoArbol; p nivel = elem.nivel; 2 System.out.println("nivel: "+nivel+" "+p.clave+" "); 4 5 if (p.iz != null) { elem = new tElemento (p.iz, nivel+1); cola.encolar (elem); ↑2 2 ↑3 2 } if (p.de != null) { p = ↑1 elem = new tElemento(p.de, nivel+1); ↑1 1 nivel =1; cola.encolar(elem); clave 1, Nivel 1 } } } } 3 8 1 3 8 nodoArbol 1 p 2 while (! cola.colaVacia()) { elem = cola.desencolar(); ↑2 2 referencia = elem.nodoArbol; nivel = elem.nivel; System.out.println("nivel: "+nivel+" "+p.clave+" "); if (p.iz != null) { elem = new tElemento (p.iz,nivel+1); cola.encolar(elem); } if (p.de != null) { elem = new tElemento (p.de,nivel+1); cola.encolar(elem); } } 3 4 5 ↑3 2 ↑4 3 ↑5 3 p = ↑2 nivel =2; clave 1, nivel 1 clave 2, nivel 2 nodoArbol p 1 2 4 3 5 ↑4 3 ↑3 2 8 p = ↑3 nivel =3; clave 1, nivel 1 clave 2, nivel 2 8 ↑5 3 ↑8 3 nodoArbol 1 p 2 while (! cola.colaVacia()) { elem = cola.desencolar(); 4 5 8 referencia = elem.nodoArbol; nivel = elem.nivel; System.out.println("nivel: "+nivel+" "+p.clave+" "); ↑5 3 ↑8 3 if (p.iz != null) { p = ↑4; n =2; elem = new tElemento (p.iz,nivel+1); ↑4 3 clave 1, nivel 1 cola.encolar(elem); clave 2, nivel 2 } clave 3, nivel 2 clave 4, nivel 3 if (p.de != null) { elem = new tElemento (p.de,nivel+1); nodoArbol cola.encolar(elem); 1 } } 3 2 4 p p = ↑5; n =3; clave 1, nivel 1 clave 2, nivel 2 clave 3, nivel 2 clave 4, nivel 3 clave 5, nivel 3 ↑8 3 ↑5 3 5 3 8 nodoArbol 1 2 3 p 4 while (! cola.colaVacia()) { elem = cola.desencolar(); referencia = elem.nodoArbol; ↑8 3 nivel = elem.nivel; System.out.println("nivel: "+nivel+" "+p.clave+" "); if (p.iz != null) { elem = new tElemento (p.iz,nivel+1); cola.encolar(elem); } if (p.de != null) { elem = new tElemento (p.de,nivel+1); cola.encolar(elem); } } 5 8 p = ↑8; n =3; clave 1, nivel 1 clave 2, nivel 2 clave 3, nivel 2 clave 4, nivel 3 clave 5, nivel 3 Clave 8, nivel 3 Verificar si dos árboles son iguales static boolean pruebaIguales (Arbol arboA, Arbol arbolB) { return sonIguales (arbol1.raiz, arbol2.raiz); } static boolean sonIguales (NodoArbol a, NodoArbol b) { boolean resul ; if ((a == null) && (b == null)) resul = true; else if ((a == null) || (b == null)) resul = false; else if (a.clave == b.clave) resul = sonIguales (a.iz, b.iz) && sonIguales (a.de, b.de); else resul = false; return resul; } Arbol Binario de Búsqueda contenido en lista static boolean estaContenido (NodoArbol nodoArbol, NodoLista nodoLista) { boolean seguir, saltar; if (nodoArbol == null) seguir = true; else { seguir = estaContenido (nodoArbol.iz, nodoLista); if (seguir && (nodoLista != null)) if (nodoArbol.clave < nodoLista.clave) seguir = false; else { saltar = true; while ((nodoLista != null) && saltar) if (nodoArbol.clave == nodoLista.clave) saltar = false; else nodoLista = nodoLista.sig; if (!saltar) seguir = estaContenido (nodoArbol.de, nodoLista.sig); else seguir = false; } else seguir = false; } return seguir; } static boolean estaContenido (Arbol arbol, Lista lista) { return estaContenido (arbol.raiz, lista.inicio); }