Arboles Binarios
Páginas: 9 (2085 palabras)
Publicado: 31 de enero de 2016
República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Universitaria
Colegio Universitario Francisco de Miranda
PNF en Informática
Sección I07-201
Cátedra: Algorítmica y Programación III Mod. III
ARBOLES
Introducción
El árbol es una estructura de datos muyimportante en informática. Los árboles son estructuras no lineales, al contrario de los arrays y las listas enlazadas que constituyen estructuras lineales.
Los árboles son utilizados para representar formular algebraicas, para búsquedas grandes y complejas en listas dinámicas y en aplicaciones diversas tales como algoritmos de cifrado e inteligencia artificial.
Los sistemas operativos almacenansus archivos en árboles o estructuras similares a árboles. Los árboles se utilizan en diseño de compilares, procesos de textos y algoritmos de búsquedas.
Estructura de un árbol binario
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierdacomo hijo izquierdo y el nodo de la derecha como hijo derecho.
La estructura de un arbol binario se construye con nodos. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos de tipo punteros, uno al sub-arbol izquierdo y otro al sub-arbol derecho, que se conocen como puntero izquierdo y puntero derecho, respectivamente, un valor NULL indica un arbol o un sub-arbol vacio.
Eltipo de datos correspondiente a la estructura de un nodo de un árbol binario es el siguiente:
Nodo
SubarbolIzquierdo
Datos
SubarbolDerecho
Fin nodo
Operaciones en arboles binarios
Una vez que se tiene creado un árbol binario, se pueden realizar diversas operaciones sobre él. El hacer uso de una operación u otradependerá de la aplicación que se le quiera dar al árbol. Algunas de las operaciones típicas que se realizan en arboles binarios son:
Operaciones:
Todas las operaciones se pueden realizar recorriendo el árbol de un modo sistemático. El recorrido de un árbol es la operación de visita al árbol, o lo que es lo mismo, la visita a cada nodo del árbol una vez o solo una. La visita de un árbol esnecesaria en muchas ocasiones, por ejemplo, si se desea imprimir la información contenida en cada nodo.
Arboles de expresión
Los árboles de expresión representan el código en una estructura de datos en forma de árbol donde cada nodo es una expresión, por ejemplo, una llamada a método o una operación binaria como x < y.
Recorrido de un árbol
Un recorrido de un árbol binario requiere que cada nodo delárbol sea procesado (visitado) una vez y sólo una en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido, profundidad y anchura. El recorrido en profundidad, el proceso exige un camino desde la raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras, en el recorrido en profundidad, todos losdescendientes de un hijo se procesan antes del siguiente hijo.
En el recorrido en anchura, el proceso se realiza horizontalmente desde la raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En otras palabras, en el recorrido en anchura, cada nivel se procesa totalmente antes de que comience el siguiente nivel. Ladesignación tradicional de los recorridos utiliza un nombre para el nodo raíz (N), para el subárbol izquierdo (I) y para el subárbol derecho (D).
El recorrido en orden previo (Orden de primero profundidad) sigue 3 operaciones:
Visitar la raíz.
Recorrer el subárbol izquierdo en orden previo.
Recorrer el subárbol derecho en orden previo.
El recorrido en orden (Orden simétrico) es así: ...
Ministerio del Poder Popular para la Educación Universitaria
Colegio Universitario Francisco de Miranda
PNF en Informática
Sección I07-201
Cátedra: Algorítmica y Programación III Mod. III
ARBOLES
Introducción
El árbol es una estructura de datos muyimportante en informática. Los árboles son estructuras no lineales, al contrario de los arrays y las listas enlazadas que constituyen estructuras lineales.
Los árboles son utilizados para representar formular algebraicas, para búsquedas grandes y complejas en listas dinámicas y en aplicaciones diversas tales como algoritmos de cifrado e inteligencia artificial.
Los sistemas operativos almacenansus archivos en árboles o estructuras similares a árboles. Los árboles se utilizan en diseño de compilares, procesos de textos y algoritmos de búsquedas.
Estructura de un árbol binario
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierdacomo hijo izquierdo y el nodo de la derecha como hijo derecho.
La estructura de un arbol binario se construye con nodos. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos de tipo punteros, uno al sub-arbol izquierdo y otro al sub-arbol derecho, que se conocen como puntero izquierdo y puntero derecho, respectivamente, un valor NULL indica un arbol o un sub-arbol vacio.
Eltipo de datos correspondiente a la estructura de un nodo de un árbol binario es el siguiente:
Nodo
SubarbolIzquierdo
Datos
SubarbolDerecho
Fin nodo
Operaciones en arboles binarios
Una vez que se tiene creado un árbol binario, se pueden realizar diversas operaciones sobre él. El hacer uso de una operación u otradependerá de la aplicación que se le quiera dar al árbol. Algunas de las operaciones típicas que se realizan en arboles binarios son:
Operaciones:
Todas las operaciones se pueden realizar recorriendo el árbol de un modo sistemático. El recorrido de un árbol es la operación de visita al árbol, o lo que es lo mismo, la visita a cada nodo del árbol una vez o solo una. La visita de un árbol esnecesaria en muchas ocasiones, por ejemplo, si se desea imprimir la información contenida en cada nodo.
Arboles de expresión
Los árboles de expresión representan el código en una estructura de datos en forma de árbol donde cada nodo es una expresión, por ejemplo, una llamada a método o una operación binaria como x < y.
Recorrido de un árbol
Un recorrido de un árbol binario requiere que cada nodo delárbol sea procesado (visitado) una vez y sólo una en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido, profundidad y anchura. El recorrido en profundidad, el proceso exige un camino desde la raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras, en el recorrido en profundidad, todos losdescendientes de un hijo se procesan antes del siguiente hijo.
En el recorrido en anchura, el proceso se realiza horizontalmente desde la raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En otras palabras, en el recorrido en anchura, cada nivel se procesa totalmente antes de que comience el siguiente nivel. Ladesignación tradicional de los recorridos utiliza un nombre para el nodo raíz (N), para el subárbol izquierdo (I) y para el subárbol derecho (D).
El recorrido en orden previo (Orden de primero profundidad) sigue 3 operaciones:
Visitar la raíz.
Recorrer el subárbol izquierdo en orden previo.
Recorrer el subárbol derecho en orden previo.
El recorrido en orden (Orden simétrico) es así: ...
Leer documento completo
Regístrate para leer el documento completo.