Arboles binarios
Páginas: 6 (1383 palabras)
Publicado: 4 de marzo de 2014
ARBOLES BINARIOS
Los árboles son una de las estructuras de datos más comunes en la programación de software para almacenar y procesar datos, gracias a sus innumerables aplicaciones. En este post veremos algunas características de los árboles y las implementaciones de algunos métodos y propiedades usando C#.
Informalmente, un árbol es una colección de objetos llamados nodos, de los cualesuno constituye la raíz. Sobre los nodos se define una relación “ser padre” que garantiza la estructura jerárquica entre los nodos. Como se puede apreciar, un hijo de un nodo de un árbol, es también un árbol, por lo que podemos definir un árbol recursivamente como una estructura formada por un nodo raíz r y un conjunto de árboles cuyas raíces son los hijos de r.
Un nodo es hoja si no es padre deningún nodo.
Un árbol que no tenga ningún nodo es un árbol nulo.
Un árbol es ordenado si existe una relación de orden entre los hijos de un nodo.
Un árbol binario es un árbol donde cada nodo tiene como máximo dos hijos. De igual forma podemos definir un árbol k-ario, donde cada nodo tiene a lo sumo k hijos.
Un árbol binario ordenado es un árbol donde cada nodo tiene un hijo izquierdo y un hijoderecho.
PARA QUE SIRVEN
Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados defineel tipo de recorrido. Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.
Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz conrespecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).
Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos.Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.
COMO FUNCIONAN Y LOS TIPOS DE RECORRIDO.
Existen varias formas de recorrer un árbol, en dependencia de cómo estén ordenados, los recorridos más comunes son preorden, entreorden, a lo ancho y postorden.
PreOrden: Este recorrido imprime primero los padres y después los hijosen preorden.
EntreOrden: Primero se imprime el primer hijo izquierdo con su recorrido
EntreOrden, después la raíz, y luego el segundo hijo en EntreOrden, y así sucesivamente los restantes hijos. Si el árbol en cuestión es un árbol binario ordenado (ABB) el recorrido sería exactamente una ordenación de los elementos de dicho árbol, ya que hay un orden establecido entre los hijos, pero luegotrataremos un post completo sobre los árboles binarios de búsqueda, que tienen algunas aplicaciones y propiedades importantes.
Para el ejemplo anterior tendríamos el siguiente recorrido: B, A, D, C, E, F
PostOrden: Se recorren primero los hijos y luego los padres en postorden.
El recorrido postorden para el ejemplo sería B, D, E, F, C, A
Por último, le dejo algunos códigos que hice hacealgunos años donde pueden ver otros métodos y funcionalidades de la clase árbol (añadir elementos, eliminar, altura, espejo, ancho, recorridos, dibujar arbol, etc), también añadí la clase árbol binario, que hereda de la clase árbol, y una aplicación de consola donde se prueban varios métodos de estas clases.
Los Árboles tiene 3 Recorridos Diferentes los cuales son:
Pre-Orden
In-Orden
Post-Orden...
Los árboles son una de las estructuras de datos más comunes en la programación de software para almacenar y procesar datos, gracias a sus innumerables aplicaciones. En este post veremos algunas características de los árboles y las implementaciones de algunos métodos y propiedades usando C#.
Informalmente, un árbol es una colección de objetos llamados nodos, de los cualesuno constituye la raíz. Sobre los nodos se define una relación “ser padre” que garantiza la estructura jerárquica entre los nodos. Como se puede apreciar, un hijo de un nodo de un árbol, es también un árbol, por lo que podemos definir un árbol recursivamente como una estructura formada por un nodo raíz r y un conjunto de árboles cuyas raíces son los hijos de r.
Un nodo es hoja si no es padre deningún nodo.
Un árbol que no tenga ningún nodo es un árbol nulo.
Un árbol es ordenado si existe una relación de orden entre los hijos de un nodo.
Un árbol binario es un árbol donde cada nodo tiene como máximo dos hijos. De igual forma podemos definir un árbol k-ario, donde cada nodo tiene a lo sumo k hijos.
Un árbol binario ordenado es un árbol donde cada nodo tiene un hijo izquierdo y un hijoderecho.
PARA QUE SIRVEN
Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados defineel tipo de recorrido. Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.
Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz conrespecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).
Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos.Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.
COMO FUNCIONAN Y LOS TIPOS DE RECORRIDO.
Existen varias formas de recorrer un árbol, en dependencia de cómo estén ordenados, los recorridos más comunes son preorden, entreorden, a lo ancho y postorden.
PreOrden: Este recorrido imprime primero los padres y después los hijosen preorden.
EntreOrden: Primero se imprime el primer hijo izquierdo con su recorrido
EntreOrden, después la raíz, y luego el segundo hijo en EntreOrden, y así sucesivamente los restantes hijos. Si el árbol en cuestión es un árbol binario ordenado (ABB) el recorrido sería exactamente una ordenación de los elementos de dicho árbol, ya que hay un orden establecido entre los hijos, pero luegotrataremos un post completo sobre los árboles binarios de búsqueda, que tienen algunas aplicaciones y propiedades importantes.
Para el ejemplo anterior tendríamos el siguiente recorrido: B, A, D, C, E, F
PostOrden: Se recorren primero los hijos y luego los padres en postorden.
El recorrido postorden para el ejemplo sería B, D, E, F, C, A
Por último, le dejo algunos códigos que hice hacealgunos años donde pueden ver otros métodos y funcionalidades de la clase árbol (añadir elementos, eliminar, altura, espejo, ancho, recorridos, dibujar arbol, etc), también añadí la clase árbol binario, que hereda de la clase árbol, y una aplicación de consola donde se prueban varios métodos de estas clases.
Los Árboles tiene 3 Recorridos Diferentes los cuales son:
Pre-Orden
In-Orden
Post-Orden...
Leer documento completo
Regístrate para leer el documento completo.