6530994
Description
Flashcards by Aldair Raya, updated more than 1 year ago
|
Created by Aldair Raya
about 8 years ago
|
|
| Question | Answer |
| Árboles | un árbol representa una jeraquía ejemplos: estructura organizativa de una empresa tabla de contenido de un libro |
| Sistema de ficheros de Unix o DOS/Windows | Representación: Conjuntos anidados Paréntesis anidados Indentación Grafo Representación más usual: grafo |
| Terminología de Arboles | A es el nodo raíz B es el padre de D y E C es el primo de B D y E son los hijos de B D, E, F, G, I son nodos externos o hojas A, B, C, H son nodos internos La profundidad (nivel) de E es 2 La altura del árbol es 3 El grado del nodo B es 2 Propiedad: (#aristas) = (#nodos) - 1 |
| Arboles binarios | Arbol ordenado: el hijo de cada nodo está ordenado Arbol binario: árbol ordenado con todos los nodos internos de grado 2 Definición recursiva de árbol binario: Un árbol binario es: - un nodo externo (hoja) o - un nodo interno (la raíz) y dos árboles binarios (subárbol izquierdo y subárbol derecho) |
| Propiedades de Arboles Binarios | (# nodos externos) = (# nodos internos) + 1 (# nodos nivel i) 2 i (# nodos externos) 2 altura (altura) log2 (# nodos externos) (altura) log2 (# nodos) - 1 (altura) (# nodos internos) - ((# nodos) - 1)/2 |
| TDAs para Arboles | Métodos contenedor genéricos -size(), isEmpty(), elements() Métodos contenedor posicionales -positions(), swapElements(p,q), replaceElement(p,e) Métodos consulta -isRoot(p), isInternal(p), isExternal(p) Métodos acceso -root(), parent(p), children(p) Métodos actualización -específico de la aplicación |
| TDAs para Arboles Binarios | Métodos acceso -leftChild(p), rightChild(p), sibling(p) métodos actualización -expandExternal(p), removeAboveExternal(p) -otros métodos específicos de la aplicación |
Want to create your own Flashcards for free with GoConqr? Learn more.