Arboles binarios
Páginas: 10 (2353 palabras)
Publicado: 29 de mayo de 2011
Árboles binarios
10.1 Concepto de árbol
Un Árbol Binario es un conjunto de finito de Elementos (Nodos), de forma que:
• El Árbol Binario es Vació si no tiene ningún elemento en el.
• El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho. No pueden tener más de dos hijos (de ahí el nombre "binario")
10.2 Árboles binarios10.2.1 Terminología
La terminología que por lo regular se utiliza para el manejo de arboles 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 nodos serán hermanos si son descendientes directos de un mismonodo.
Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
Nodo anterior: Es un nodo que no es raíz ni terminal.
Grado: Es el número de descendientes directos de un determinado nodo.
Grado de un árbol: Es el máximo grado de 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 laraí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 directos longitud de camino 2 y así sucesivamente.
10.2.2 Nivel de unnodo y altura de un árbol
Nivel de un nodo:
El nivel de un nodo se asigna en función al criterio siguiente:
La raíz tiene nivel 1.
Si un nodo tiene nivel N, sus hijos tendrán nivel N+l
Altura de un árbol
Es la altura de la raíz, o 0 si el árbol es vacío
10.2.3 Árboles binario, lleno y completo
Arbol completo
• Son aquellos arboles en los que todos sus nodos excepto los delultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.
• Considere un árbol binario T. El árbol binario T se dice que es completo si todos sus niveles, excepto posiblemente el ultimo, tienen el máximo numero de nodos posibles y si todos lo9s nodos del ultimo nivel están situados. Lo más posible a la izquierda. Así, solo existe un único árbol completo Tn conexactamente n nodos.
10.2.4 Recorrido de un árbol binario
10.5 Recorrido de un árbol
Recorrer el Árbol significa que cada nodo sea procesado una vez y solo una en un secuencia determinada. Existen 2 enfoques generales
• Recorrido en amplitud
Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
• Recorrido en profundidad
Recorreel árbol por subárboles.
10.3 Árboles de expresión
Un árbol binario de expresión (ABE) es un árbol binario utilizado para representar una expresión aritmética de la siguiente manera:
• Cada hoja contiene un operando.
• Cada nodo interior contiene un operador aritmético.
Un ABE tiene información implícita sobre prioridad de operadores y asociatividad.
Sea T un ABE compuesto de un nodo N ysubárboles izquierdo Ti y derecho Td. La evaluación de T se efectúa de acuerdo al siguiente algoritmo:
• Si Ti y Td son árboles vacíos, entonces el valor de T es el valor contenido en N.
• Si Ti y Td son árboles no vacíos, entonces el valor de T es el valor de Ti operado con el valor de Td según el operador contenido en N.
10.4 Construcción de un árbol binario
Hemos dicho que los árbolesson estructuras de datos, generalmente ordenadas; aunque pueden no estarlo, la mayoría de sus aplicaciones requieren que lo estén. Al igual que en las listas, el criterio de ordenación puede ser cualquiera. Sin embargo, es importante señalar que la disposición final de los nodos depende del orden de creación. Una vez establecido el criterio de ordenación que se utilizará, el proceso de...
10.1 Concepto de árbol
Un Árbol Binario es un conjunto de finito de Elementos (Nodos), de forma que:
• El Árbol Binario es Vació si no tiene ningún elemento en el.
• El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho. No pueden tener más de dos hijos (de ahí el nombre "binario")
10.2 Árboles binarios10.2.1 Terminología
La terminología que por lo regular se utiliza para el manejo de arboles 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 nodos serán hermanos si son descendientes directos de un mismonodo.
Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
Nodo anterior: Es un nodo que no es raíz ni terminal.
Grado: Es el número de descendientes directos de un determinado nodo.
Grado de un árbol: Es el máximo grado de 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 laraí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 directos longitud de camino 2 y así sucesivamente.
10.2.2 Nivel de unnodo y altura de un árbol
Nivel de un nodo:
El nivel de un nodo se asigna en función al criterio siguiente:
La raíz tiene nivel 1.
Si un nodo tiene nivel N, sus hijos tendrán nivel N+l
Altura de un árbol
Es la altura de la raíz, o 0 si el árbol es vacío
10.2.3 Árboles binario, lleno y completo
Arbol completo
• Son aquellos arboles en los que todos sus nodos excepto los delultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.
• Considere un árbol binario T. El árbol binario T se dice que es completo si todos sus niveles, excepto posiblemente el ultimo, tienen el máximo numero de nodos posibles y si todos lo9s nodos del ultimo nivel están situados. Lo más posible a la izquierda. Así, solo existe un único árbol completo Tn conexactamente n nodos.
10.2.4 Recorrido de un árbol binario
10.5 Recorrido de un árbol
Recorrer el Árbol significa que cada nodo sea procesado una vez y solo una en un secuencia determinada. Existen 2 enfoques generales
• Recorrido en amplitud
Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
• Recorrido en profundidad
Recorreel árbol por subárboles.
10.3 Árboles de expresión
Un árbol binario de expresión (ABE) es un árbol binario utilizado para representar una expresión aritmética de la siguiente manera:
• Cada hoja contiene un operando.
• Cada nodo interior contiene un operador aritmético.
Un ABE tiene información implícita sobre prioridad de operadores y asociatividad.
Sea T un ABE compuesto de un nodo N ysubárboles izquierdo Ti y derecho Td. La evaluación de T se efectúa de acuerdo al siguiente algoritmo:
• Si Ti y Td son árboles vacíos, entonces el valor de T es el valor contenido en N.
• Si Ti y Td son árboles no vacíos, entonces el valor de T es el valor de Ti operado con el valor de Td según el operador contenido en N.
10.4 Construcción de un árbol binario
Hemos dicho que los árbolesson estructuras de datos, generalmente ordenadas; aunque pueden no estarlo, la mayoría de sus aplicaciones requieren que lo estén. Al igual que en las listas, el criterio de ordenación puede ser cualquiera. Sin embargo, es importante señalar que la disposición final de los nodos depende del orden de creación. Una vez establecido el criterio de ordenación que se utilizará, el proceso de...
Leer documento completo
Regístrate para leer el documento completo.