Ipads

Instituto Tecnológico Superior de Coatzacoalcos
Ingeniería en Informática

Matemáticas Discretas
Unidad 6
TEORÍA DE GRAFOS
Actividad 1
Árboles
Docente: Ing. Leovigilda HuescA Herrera
Alumn0: GOMEZ HERNANDEZ JOSUE
INDICE

OBJETIVO…………………………………….. 3
INTRODUCCIÓN…………………………….. 4
ARBOLES…………………………………….. 5
COMPONENTES……………………………. 6
PROPIEDADES……………………………… 7CLASIFICACIÓN…………………………….. 8
ARBOLES CON PESO……………………………….………… 9
RECORRIDO DE UN ARBOL…………………… ……………… 10
CONCLUSIÓN……………………………….. 11
BIBLIOGRAFÍA………………………………. 12

OBJETIVO

Concepto de Árbol, sus estructuras y aplicaciones.

INTRODUCCIÓN

Estructura de datos  llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como porejemplo registros, árboles genealógicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementada fácilmente en la computadora.

Arboles

Los árboles forman una de las subclases de gráficas que más se utilizan. La ciencia de la computación hace uso de los árboles ampliamente, especialmente para organizar y relacionar datos en una base de datos. Los árboles surgenen problemas teóricos como el tiempo óptimo para ordenar.

Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles.

Una forma particular de árbol puede ser la estructura vacía. Un árbol es un grafo simple en el cual existe un único camino entre cada par devértices.

Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. Sea G = (V, A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.

Ejemplo de un árbol: 

Componentes (raíz, hoja, padre, hijo, descendientes, ancestros)

Un árbol está dividoen tres subconjuntos separados.

-El primer subconjunto contiene un único elemento llamado raíz del árbol.
-Los otros 2 subconjuntos son por si mismos árboles binarios y se les conoce como subárboles izquierdo y derecho del árbol original. Cada elemento de un árbol binario se denomina nodo. La ausencia de una ramificación indica un subárbol vacío.
-Si A es la raíz de un árbol binario y B esla raíz de su subárbol izquierdo o derecho, se dice que A es el padre de B y se dice que B es el hijo izquierdo o derecho de A.
-Un nodo que no tiene hijos se denomina hoja. El nodo n1 es un ancestro del nodo n2 (y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2. 2 nodos son hermanos si son los hijos izquierdo y derecho del mismo padre.
-Si cada nodo que noes hoja es un árbol binario tiene subárboles izquierdo y derecho que no están vacíos, el elemento se clasifica como árbol estrictamente binario.
-Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbolpueden seguirle varios elementos.
-Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para elanálisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro.

Raíz: Nodo que constituye la única entrada a la estructura (por ello es necesario tener un puntero sobre él).
Ramas o Arcos: Conexión entre dos nodos del árbol que representa una relación de jerarquía.
Hojas: Nodo sin hijos

Propiedades

Un árbol es un grafo simple en el...