Arboles transmision de datos

ARBOLES
ESTRUCTURAS DE DATOS 2006

DEFINICION
Un árbol (tree) es un conjunto finito de nodos. Es una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

Los árboles representan las estructuras no lineales y dinámicas. No lineales,puesto que a cada elemento del árbol pueden Dinámicas, seguirle varios elementos. puesto que la estructura árbol puede cambiar durante la ejecución del programa.

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

EJEMPLOS DE ARBOLES

Figura 1 :Árboles

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

CARACTERISTICAS Y PROPIEDADESDE LOS ÁRBOLES EN GENERAL
Todo árbol que no es vacío, tiene un único nodo raíz. Un nodo X es descendiente directo de un nodo Y, si el nodo X apunta al nodo Y. X es hijo de Y. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es el padre de Y. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos. Todo nodo que no tieneramificaciones (hijos) se conoce con el nombre de terminal u hoja.

Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

CARACTERISTICAS Y PROPIEDADES DE LOS ÁRBOLES EN GENERAL

Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo gradode todos los nodos del árbol. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. Altura del árbol es el máximo número de niveles de todos los nodos del árbol. Rama es un camino desde el nodo raíz a una hoja.

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

Figura 2 :Árbol General

A raízdel árbol B es el hijo de A. C es hijo de A. B es padre de D. D es padre de I. B y C son hermanos. D, E, F son hermanos. I, E, J, K, G, L son hojas. B, D, F, C y H son nodos interiores. Nivel del nodo A es 1. Nivel del nodo E es 3. La altura del árbol es 4.

El grado de nodo A es 2 El grado de nodo B es 3 El grado de nodo C es 2 El grado de nodo D es 1 El grado de nodo E es 0 Grado del árbol es 3Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

ÁRBOLES BINARIOS
Definición 1: Un árbol binario es un árbol en el que cada nodo no puede tener mas de dos hijos o descendientes. Es un árbol de grado 2. Definición 2: Un árbol binario es un conjunto finito de nodos, el cual puede ser vacío o un conjunto que consta de un nodo raíz enlazado a dos árboles binariosdisjuntos denominados subárbol izquierdo y subárbol derecho.

Figura 3 :Árboles Binarios

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA En un árbol binario los hijos se conocen como hijo izquierdo e hijo derecho Un nodo que no tiene hijos se denomina hoja. En la figura 4 B, C son hojas. El nodo raíz se dice que está en el nivel Oen el árbol. Los nodos B y C están en el nivel 1. (figura 4) Altura del árbol se define como el nivel más alto del árbol. En la figura 4 la altura del árbol es 2.

Figura 4 :Árbol Binario

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA Un árbol binario está balanceado (equilibrado) si cada nodo tiene exactamente dos hijos o notiene hijos y si cada hoja está al mismo nivel.

Figura 5 :Árbol Binario Equilibrado

Figura 6 :Árbol Binario no Equilibrado

Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA Los subárboles izquierdo y derecho de un árbol binario deben ser subconjuntos disjuntos, esto es, ningún nodo puede estar en ambos subárboles. Ejemplo:

(a)...