Definición de arboles

República bolivariana de Venezuela

Ministerio de educación para el poder popular

Liceo nacional Dr. Raúl cuenca

Ciudad Ojeda – edo. Zulia

Asignatura: estructura de datos

Prof.: regulo Méndez

Realizado por:

Domingo reyes

Deivi González

Ciudad Ojeda 19 de noviembre del 2012

 Esquema

 Definición de arboles

 Características de arboles

 Tipos de arboles

 Recorrido de los arboles (pre-orden, post-orden, simétrico)

 Definición de Árboles

• 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.

•Un árbol de tipo T como una estructura homogénea, que es la concatenación de un elemento tipo T junto con un número finito de árboles disjuntos, llamados subárbols

 Características de arboles

Algunas Características y propiedades de los arboles

•Todo árbol que no este vacio, tiene un nodo único raíz

•Si un nodo X es apuntado por el nodo Y. Se dice que X es hijo de Y

•X es antecesor de Y si el nodo X apunta al nodo Y. X es padre de Y

•Todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

•Si un nodo no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja

•Todo nodo que no es raíz, ni hoja se conoce como nodo interior.

•Grado es el numero de descendientes directos de un nodo, grado de un árbol es el máximo grado de todos los nodos del árbol

•Nivel es el numero de arcos que deben recorrerse para llegar a un nodo. Raíz tiene nivel 1

•Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

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.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

 Tipos de arboles

Árboles Binarios

•Un árbol binario cada nodo puede tener como máximo dos subárbols y siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho

•Árbol binario tipo T es una estructura homogénea que es la concatenación de un elemento tipo T, llamado raíz, con dos arboles binarios disjuntos, llamados subárbol izquierdo y subárbol derecho.

•Se pueden aplicar para representar un árbol genealógico o para representar expresiones algebraicas construidas con operadores binarios

• Distintos. Cuando sus estructuras son diferentes

• Similares. Cuando sus estructuras son idénticas pero la información que contiene cada árbol es diferente.

• Equivalentes. Cuando son similares y además la información es idéntica entre los dos arboles.

• Arboles avl: Un árbol AVL (llamado así por las iníciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárbols izquierdo y derecho no difieren en más de 1.

 Recorrido de los arboles (pre-orden, post-orden, simétrico)

Árbol binario

Pre-orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre orden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo

...