17 de junio de 2009
17 de junio de 2009

UNIVERSIDAD DE GUADALAJARA
17 de junio de 2009
ÁRBOLES
CENTRO UNIVERSITARIO DE LOS ALTOS (CUALTOS)
MATEMÁTICAS DISCRETAS
LIC. EN MAT.: NANCY ULLOA FIGUEROA
ING. EN COMPUTACIÓN
2° SEMESTRE
FÁTIMA CABRERA SALAS
FÁTIMA SANDOVAL ISLAS

TEPATITLAN DE MORELOS, JALISCO

Contenido INTRODUCCIÓN 2 PROPIEDADES DE LOS ÁRBOLES 4 TEOREMAS. 5 ÁRBOLES CON TERMINAL. 7 LONGITUD DE PASEO. 7 PREFIJOS CODIFICADOS. 9 ÁRBOLES CON BUSQUEDA BINARIA. 11 ÁRBOLES GENERADORES. 13 ÁRBOLES GENERADORES MINIMOS. 14

INTRODUCCIÓN
A partir de 1920 se despertó el interés por la teoría de gráficas. Sin duda, una de las razones de este reciente interés en la teoría de gráficas es su capacidad de aplicación en campos …ver más…

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden: * El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo. * El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos en orden simétrico. * El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

PROPIEDADES DE LOS ÁRBOLES
Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes: * G es conexo y no tiene ciclos simples. * G no tiene ciclos simples y, si se añade alguna arista