Tareas Basicas

1 Curso de Estructuras de Datos Orientada a Objetos Ing. Daysi M. Erreyes P.

7.

ÁRBOLES
Analiza: Ejemplos donde se aplican los árboles: son los sistemas de ficheros, diagrama modular, eliminatorias deportivas, organigramas de empresas etc, etc… Piensa en otras aplicaciones informáticas de la vida real, en donde se utilice la estructura: Arbol, comenta con tus compañeros y con tuprofesora…..!!!

7.1. Introducción

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 el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro. Los árboles representan las estructuras no lineales y dinámicas dedatos 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 árbol pueden seguirle varios elementos. 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. Ladefinición de árbol es la siguiente: Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Formalmente se define un árbol de tipo T como una estructura homogénea que es laconcatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárbols. Una forma particular de árbol puede ser la estructura vacía. Terminología básica de la Estructura Árbol

2 Curso de Estructuras de Datos Orientada a Objetos Ing. Daysi M. Erreyes P.

Raíz: único nodo que no tiene antecesor, es decir, sin padre. Rama: arista formado entre dos nodos.Antecesor: un nodo X es el antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y. Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X. Grado de un nodo: número de descendientes directos que tiene un nodo. Grado del árbol: es el mayor grado entre sus nodos. Nodo interno: es aquel que tiene al menos un descendiente o nodo hijo. Nodo hoja(externo): nodo que no tiene descendientes o no tiene nodos hijos, posee grado 0. Descendiente directo: hijo Descendientes: hijo, nieto... Subárbol: árbol formado por un nodo y sus descendientes

Árbol binario: árbol de grado 2, en donde cada nodo tiene como mucho dos descendientes directos. Árbol multicamino: Cada nodo puede tener n descendientes directos. Lista: árbol degenerado de grado 1. Nivel:número de ramas que hay que recorrer para llegar de la raíz a un nodo; la raíz siempre tiene un nivel de 0. Profundidad de un nodo: número de predecesores.

3 Curso de Estructuras de Datos Orientada a Objetos Ing. Daysi M. Erreyes P.

Altura del árbol: profundidad máxima de cualquier nodo o el nivel más alto del árbol más

Camino: Existe un camino del nodo X al nodo Y, o si existe unasucesión de nodos que permitan llegar desde X a Y.

Formas de representar un árbol 1. Mediante un grafo:

4 Curso de Estructuras de Datos Orientada a Objetos Ing. Daysi M. Erreyes P.

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. 2. Mediante un diagrama encolumnado:

A continuación veremosen java como se puede declarar una estructura de datos básica (se indicará solamente atributos) para un árbol cualesquiera. class NodoArbol { int dato; // información del nodo // es un arbol con ramas de hasta 3; NodoArbol nodo1, nodo2, nodo3; // si queremos más ramas deberíamos declarar un array de // objetos de tipo NodoArbol o utilizar Collections, // Vector, ArrayList, que son propias de...