Matematica discreta

UNIDAD VI. ÁRBOLES

6.1 DEFINICIÓN

un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo $a$ es padre de un nodo $b$ si existe un enlace desde $a$ hasta $b$ (en ese caso, también decimos que $b$ es hijo de $a$ ). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

6.2 PROPIEDADES DE LOS ÁRBOLES

6.2.1 ÁRBOLES CON RAÍZ

Un Árbol con raíz es un árbol con un vértice

distinguido denominado raíz.

6.2.2 ÁRBOLES JERÁRQUICOS

6.2.3 ÁRBOLES PESADOS

6.2.4 ÁRBOLES BINARIOS

Un arbol binario es un arbol en el que el maximo numero de hijos de cada

nodo es 2 (hijo izquierdo e hijo derecho).

6.2.4.1 ÁRBOLES BINARIOS COMPLETOS

Un arbol binario se dice que es completo (o lleno) si todas las hojas tienen

la misma profundidad y todos los nodos internos tienen grado 2.

6.2.5 ÁRBOLES GENERADORES

6.2.6 ALTURA DE UN ÁRBOL

Se llama profundidad de un nodo a la longitud

del camino desde la raíz a ese nodo.

La altura de un árbol es la profundidad del nodo

más profundo.

6.2.7 DOMINIOS DE ÁRBOLES

6.2.8 BOSQUES

6.3 ALGORITMOS DE BÚSQUEDA DE PRIMERA PROFUNDIDAD

6.4 TEOREMA DE PRIM.

Un bosque es un grafo acíclico no dirigido.

l Un grafo acíclico, no dirigido y conexo es un

árbol (libre).