cbtis125

ÁRBOLES

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. 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.
Un árbol es una estructura jerárquica aplicada sobre una colección de elementos u objetosllamados 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.
Existen diferentes formas de representación de un árbol, entre las más comunes se tienen las siguientes: Mediante círculos y flechas, Mediante paréntesis anidados, Mediante notación decimal de Dewey.Algunas veces se incluye entre los árboles el árbol nulo vacío, el cual, es un árbol sin nodos que se representa mediante la letra .
Cualquier nodo del árbol podría tener un número arbitrario de nodos hijos, a esto se le conoce como un árbol general, como se muestra en la siguiente figura. Si se limita el número de nodos hijos para cada nodo del árbol, digamos a un número n > 2 (llamado laaridad del árbol), entonces el árbol de aridad n es llamado n-ario.
La terminología que por lo regular se utiliza para el manejo de árboles es la siguiente:
-HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
-PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
-HERMANO. Dos nodosserán hermanos si son descendientes directos de un mismo nodo.
-HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones.
-NODO INTERIOR. Es un nodo que no es raíz ni terminal.
-GRADO. Es el número de descendientes directos de un determinado nodo.
-GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.
-NIVEL. Es el número de arcos que deben serrecorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
-ALTURA. Es el máximo número de niveles de todos los nodos del árbol.
-PESO. Es el número de nodos del árbol sin contar la raíz.
-LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directoslongitud de camino 2 y así sucesivamente.

ORDEN DE LOS NODOS. Generalmente los árboles de un nodo se ordenan de izquierda a derecha. Si no se toma en cuenta el orden de los nodos hijos, entonces se habla de un árbol no ordenado.

ÁRBOLES BINARIOS
Un árbol binario es un árbol de grado 2, en el que todo nodo del árbol tiene un subárbol binario izquierdo y derecho asociados.
Árbol BinarioCompleto o Lleno: Es un árbol binario en el que todos sus nodos, excepto las hojas, tienen siempre dos hijos (el subárbol izquierdo y el derecho) no nulos. El número de nodos de un árbol completo se calcula por la fórmula: Número de nodos = 2h-1 (donde h es la altura)
Árbol Binario Completo de Altura o Profundidad H: Es un árbol Binario Completo en donde todas las hojas están en el nivel H. Esta esuna de las pocas estructuras de árbol que se pueden representar eficientemente usando arreglos.
Una expresión es una secuencia de componentes léxicos (tokens), que siguen reglas preescritas. Un token puede ser un operador o un operando. Un árbol binario de búsqueda es un árbol en el que todo nodo existente tiene un sólo elemento y cumplen lo siguiente:


-Cada hoja es un operando.
DE-El nodo raíz y los nodos internos son operadores.
EXPRESION -Los subárboles son sub_expresiones en las que
el nodo raíz es un operador.



ÁRBOLES
BINARIOS -Todas las claves del subárbol izquierdo son menores
que la raíz.
DE - Todas las claves del subárbol derecho son mayores
BUAQUEDA que la raíz.
-Los subárboles izquierdo y derecho son también
árboles de búsqueda....