Actividad 1. Árboles y árboles binarios

La siguiente actividad te permitirá distinguir entre árbol y árbol binario, de acuerdo a sus características y aplicaciones. Por lo tanto, atiende a las siguientes indicaciones: 1. Crea un archivo de texto.

2. Define árbol y desarrolla un ejemplo donde se expliquen las diferentes ramificaciones.

3. Define árbol binario y desarrolla un ejemplo donde se expliquen las diferentes ramificaciones.

4. Posterior a ello, explica la diferencia entre un árbol y un árbol binario, utiliza la representación a través de gráficas, ilustraciones, etc.

Ya que identificaste las diferencias entre los árboles y árboles binarios: 5. Guarda la actividad con el nombre DABD_U3_A1_XXYZ. Sustituye las XX por las dos primeras letras de tu primer nombre, la Y por la inicial de tu primer apellido y la Z por la inicial de tu segundo apellido.

Definición de Árbol

Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja.

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Esto son definiciones simples. Pero las características que implican no lo son tanto.1

Un árbol es una colección de elementos, llamados nodos, uno de los cuales se distingue con el nombre de raíz, los cuales mantienen una relación (parentesco) que define una estructura jerárquica entre ellos.

Propiedades de los arboles:

Tienen un nodo al que se le llama raíz del árbol. Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz

no tiene ninguna). Existe una ruta única del nodo raíz a todos los demás nodos del árbol.

1 http://www.c.conclase.net/edd/?cap=006

Si hay una ruta <a,b>, entonces a „b‟ se le denomina „hijo‟ de „a‟ y es el nodo raíz de un subárbol.

De manera formal, un árbol se puede definir en forma recursiva mediante las reglas siguientes:

El conjunto vacío de nodos es un árbol, llamado nulo o vacío. Un nodo es un árbol, el cual es, asimismo, la raíz del árbol.

Si n, es un nodo y T1, T2, . . . , Tk son árboles con raíces n1, n2, . . . , nk, respectivamente, se puede construir un nuevo árbol haciendo n el padre de los nodos n1, n2, . . . , nk. En este árbol n es la raíz y T1, T2, . . . , Tk son los subárboles de la raíz. Los nodos n1, n2, . . . , nk se conocen como los hijos del nodo n.

Si n, es un nodo y T1, T2, . . . , Tk son árboles con raíces n1, n2, . . . , nk, respectivamente, se puede construir un nuevo árbol haciendo n el padre de los nodos n1, n2, . . . , nk . En este árbol n es la raíz y T1, T2, . . . , Tk son los subárboles de la raíz. Los nodos n1, n2, . . . , nk se conocen como los hijos del nodo n.

Un camino de un nodo n1 a un nodo nk es una secuencia de nodos n 1, n2, ... , nk de tal manera que ni es padre de ni+1 para i = 1, 2, . . . , k-1.

La longitud de un camino es uno menos que el número de nodos en el camino.

Existe un camino de longitud 0 de un nodo a sí mismo.

Si existe un camino de un nodo a a un nodo b, entonces se dice que a es un ancestro de b y que b es un descendiente de a.

Un ancestro o descendiente de un nodo diferente de sí mismo se dice que es un ancestro o descendiente propio, respectivamente.

Otro ejemplo seria

Definiremos varios conceptos. En relación con otros nodos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.

En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.

Definición de Árbol Binario

Un árbol ordenado es aquel en el cual la distribución de las ramas sigue cierto orden. Los árboles ordenados de grado 2 son de especial interés puesto que representan una de las estructuras de datos más importante en computación, conocida como árboles binarios.

Un árbol binario es un árbol nulo o un árbol cuyos nodos tienen a lo sumo dos hijos. Los hijos de un árbol binario se pueden denotar como hijo izquierdo e hijo derecho.2

Un árbol binario se dice que es completo si cada nodo ó es una hoja o tiene dos hijos.

Un árbol binario completo se dice que está balanceado si al numerar sus nodos por profundidad desde la raíz hasta las hojas, de izquierda a derecha, al encontrar la primera hoja todos los nodos numerados siguientes son hojas.

Aplicaciones de Árboles Binarios

Representación de Arboles Binarios

2 http://www.uaeh.edu.mx/docencia/P_Presentaciones/icbi/asignatura/Cap6ARBOLES.pdf

Programación Orientada a Objetos.

La Clase Árbol

Diferencia entre un árbol y un árbol binario, utiliza la representación a través de gráficas, ilustraciones.

Todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques generales es isomorfo al conjunto de los árboles binarios. En efecto, las propiedades vistas en los árboles binarios se siguen cumpliendo en los árboles generales. 4

Ejemplos de las diferencias de Árboles y Arboles Binarios

3 http://delta.cs.cinvestav.mx/~adiaz/anadis/BinTree.pdf4 http://users.dcc.uchile.cl/~bebustos/apuntes/cc30a/Estructuras/

Árbol

Árbol Binario