Programacion De Arboles

Páginas: 15 (3516 palabras) Publicado: 13 de junio de 2012
Capítulo I.
Arboles

I. Estructuras de datos tipo árbol.
1. Definición y Concepto
Los árboles representan las estructuras no Lineales y dinámica de datos más importante en computación. Dinámica ya que la estructura árbol puede cambiar durante la ejecución del programa. No lineal, ya que cada elemento del árbol puede seguir varios elementos.


Árboles Generales
Un árbol es unaestructura jerárquica sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz, creándose así una relación o parentesco utilizándose términos como: padre, hijo, sucesor, ancestro.
Existen diferentes formas de representar un árbol:


• Diagrama de ven,
• anidación de paréntesis,
• notación indentada,
• Notación de Dawey.• grafos.
Consigna de aprendizaje
Objetivo: Conoce las distintas formas en que puede ser representado un árbol.
Anidación de paréntesis: (A(B(D(I),E,F(J,K)),C(G,H(L)))).
Representa en:
Diagrama de ven, notación indentada, Notación de Dawey. grafos.


Los árboles tiene una gran variedad de aplicaciones por ejemplo: para representar formulasmatemáticas, para registrar la inf. Histórica de un campeonato de tenis, para un árbol genealógico, para analizar circuitos, entre otros.

Características y propiedades de los árboles.
a. Todo árbol que no es vacío, tiene un único nodo raíz.
b. un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y, en este caso X es hijo de Y.
c. un nodo X esantecesor directo de un nodo Y si el nodo X apunta al nodo Y, por lo tanto X será el padre de Y.
d. todos los nodos que son descendientes directos de un mismo nodo padre, son hermanos.
e. Todo nodo que no tiene ramificaciones o sea hijos, se conoce como terminal u hoja.
f. Todo nodo que no es raíz, ni es terminal u hoja se conocerá con el nombre de nodo interior.
g. Grado es el númerode descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos lo nodos del árbol.
h. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo.
i. Altura del árbol es el máximo número de niveles de todos los nodos del árbol.


Longitud de camino interno y externo.
Se define la longitud de camino X como el número dearcos que serán recorridos para llegar desde la raíz al nodo X.


Longitud de camino Interno.
La longitud de camino interno es la suma de las longitudes de camino de todos los nodos del árbol. Se calculará a través de la siguiente formula.


LCI= Ni * I
Donde I representa el nivel del árbol y Ni el número de nodos en el nivel i.
La media de LCI se calculadividiendo la LCI entre el número de nodos del árbol n, se expresa: LCIM= LCI / n


Longitud de camino Externo.
Será necesario definir primero los términos de árbol extendido y nodo especial. Un árbol extendido es aquel en el que el número de hijos de cada nodo es igual al grado del árbol. Si un nodo del árbol no cumple con esta condición deberá incorporársele nodos especialestantos como sean necesario para satisfacer la condición. Los nodos especiales tienen como objetivo reemplazar las ramas vacías o nulas, no tendrán descendientes y serán representados con la forma de cuadro.
Se calculará a través de la siguiente formula.


LCE= nei * i
Donde i representa el nivel del árbol y nei el número de nodos especiales en el nivel i.La media será calculada LCEM dividiendo LCE entre el número de nodos especiales del árbol ne, se expresa:
LCEM = LCE / ne

Consigna







Referencia Bibliográfica: Estructura de Datos. Cairo Guardati. Primera edición, Mc Graw-Hill. 1993.



1.2 Árboles Binarios

En un árbol binario cada nodo puede tener como máximo dos subárboles y es necesario distinguir entre el...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Arboles En Programacion
  • Arboles programacion
  • arboles programacion
  • teoria de arboles programacion
  • Arboles lenguaje programación c++
  • Programacion- arboles
  • Arboles en programación
  • Arboles En La Programacion

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS