Estructuras de Datos: Árboles, Montículos y Recorridos

Árboles

Árbol: (N) Nodos, (N - 1) arcos dirigidos; Nodo hoja (no tiene hijos); Nodo interno (tiene al menos un hijo); Longitud del camino (N - 1); Profundidad del nodo (longitud más uno del camino desde la raíz al nodo); Altura del árbol (longitud camino más largo); Grado de nodo (número de hijos); Grado de árbol (máximo grado de nodos).

Árboles Binarios

Árbol Binario: Máximo de nodos en nivel i ( ); Máximo de nodos en AB altura h ( ); Máximo de hojas ( );

Tipos y Recorridos de Árboles Binarios de Búsqueda (ABB)

Tipos ABB: Equilibrado (altura sub. izquierdo - altura sub. derecho es => Recorridos ABB: Preorden (RID); Inorden (IRD); Postorden (IDR)

Árbol Binario de Búsqueda (ABB)

Árbol Binario de Búsqueda: elementos sub. izquierdo MENORES que raíz, elementos sub. derecho MAYORES que raíz; el Mínimo se encuentra a la izquierda y el Máximo a la derecha; la Forma depende del orden de inserción; los ABB Balanceados son ABB siempre equilibrados (en cada modificación se comprueba y modifica para reequilibrarlo);

Borrado en ABB

Borrado en ABB: buscamos el nodo que queremos borrar 1) Si es hoja, se borra; 2) nodo con solo hijo (sustituye nodo a borrar por su hijo); 3) nodo con dos hijos (busca mínimo sub. derecho, intercambian valores y borrar nodo un hijo.

Montículos (Heap)

Montículos (Heap): AB semicompleto en cada nodo del montículo el valor almacenado es menor o igual al almacenado en sus hijos; Árbol Binario Semicompleto (árbol de altura h que es completo hasta nivel h - 1 y en el nivel h los nodos se encuentran lo más a la izquierda posible; para un mismo conjunto de valores la forma de los montículos siempre será la misma.

Inserción y Borrado en Montículos

Inserción en Montículos: añade nuevo nodo al final del árbol, se compara su raíz y si es menor se hace subir. Borrado en Montículos: solo se puede consultar y borrar la Raíz, intercambia raíz por último elemento, borra último nodo, hunde elemento de raíz hasta su posición.

Implementación de Montículos

Implementación Montículos: se almacena en un vector por niveles sin huecos, último nodo del árbol es último usado del vector, Hijo izquierdo ( ), Hijo derecho ( ), Padre ( ); método add traza camino desde nodo hoja hasta raíz; método remove traza camino desde raíz hasta nodo hoja; altura del árbol es .

Colas con Prioridad

Colas con prioridad: public class NombreClase implements Comparable { public int compareTo(NombreClase otro){}}; public class Comparador1 implements Comparator{public int compare(Clase e1, Clase e2){}};

Recorrido en Anchura (BFS)

Recorrido Anchura (BFS): tomar el nodo n del grafo G y añadirlo a la cola Q; while Q no este vacía do{ u = front(q); pop(q); u = visitado; for cada v adyacente desde u do { if v no esta visitado { v = marcado; push(q, v);}}}