© NicoElNino/Shutterstock.com
En informática, los datos se pueden estructurar y atravesar de varias formas. Los árboles binarios son una forma de almacenamiento de datos jerárquicos que utiliza recorridos de árboles como método principal para visitar todos los nodos constituyentes con fines de búsqueda, clasificación y otros fines. Comprender los diversos métodos utilizados para los recorridos de árboles puede ayudarlo a completar las operaciones básicas en un árbol binario. En este artículo, explicamos qué son los recorridos de árboles, incluidos los recorridos en orden, en orden previo y en orden posterior, con ejemplos que lo ayudarán a comenzar.
¿Qué son los recorridos de árboles?
Los recorridos de árboles son los métodos que utilizan los informáticos, los desarrolladores y los ingenieros de software para atravesar un árbol binario. También se conoce como:
Recorriendo el árbol Búsqueda de árbol
Estos métodos implican visitar secuencialmente cada nodo dentro del árbol binario. A diferencia de una estructura de datos lineal como una lista enlazada o una cola, estos recorridos se pueden completar de varias maneras. Los métodos principales, que se explican a continuación, se utilizan para actualizar, eliminar, buscar, ordenar y recuperar datos de manera eficiente.
Acerca de los árboles binarios
Los árboles binarios son la forma de árbol más utilizada, que es una estructura de datos jerárquica compuesta de nodos interconectados. Cada nodo consta de referencias izquierda y derecha y un elemento de datos. Cada nodo en un árbol binario está conectado a un padre, pero cada nodo padre solo puede tener un máximo de 2 hijos. Los nodos sin hijos se llaman hojas. Los nodos que comparten un nodo principal se denominan hermanos. El nodo en la parte superior de un árbol binario se llama raíz.
Si un árbol binario está completamente lleno, se llama árbol completo. Los árboles están llenos de nodos de izquierda a derecha. Puede colocar los nodos por su altura, que es el número de aristas entre la raíz y el nodo índice, o su profundidad, que es la cantidad de aristas entre el nodo y el nodo hoja más lejano.
Utilice recorridos de árbol para visitar todos los nodos de un árbol
Una característica importante de estos recorridos es que se visitan todos los nodos del árbol. Debido a que los árboles son estructuras de datos no lineales, hay muchas formas y órdenes en los que puede asegurarse de que cada nodo se visite por turno. No hay un recorrido único, sino varios algoritmos de recorrido con los que puede trabajar.
Los recorridos de árboles son importantes
Dominar los recorridos de árboles es una habilidad clave para organizar y trabajar con datos. Esto se debe a que los árboles son una estructura de datos extremadamente común y se usan ampliamente debido a su clara representación de las relaciones y jerarquías de datos.
Puede usar estos métodos transversales y ejemplos para búsquedas o inserciones de datos más eficientes. Echemos un vistazo a los métodos clave a continuación:
Aquí hay un árbol de ejemplo:
Ilustración de una estructura de árbol.
©”TNGD”.com
1. Recorrido de preorden
Este es un tipo de recorrido primero en profundidad en el que primero se visita el nodo principal, luego el nodo secundario izquierdo y luego el nodo secundario derecho. Si se recorre un árbol utilizando el método preOrder, primero se visita el nodo raíz y luego los subárboles izquierdo y derecho secuenciales primero hasta que se recorre todo el árbol. PreOrder traversal proporciona un método eficiente para copiar un árbol.
Aquí está el ejemplo de preOrder traversal para el árbol anterior: A > B > D > E > C > F > G
Y aquí está el algoritmo de preorden:
Algoritmo para el PreOrder Traversal de una estructura de árbol.
©”TNGD”.com
2. Recorrido InOrder
Este es un tipo de recorrido primero en profundidad donde se visita el nodo secundario izquierdo, luego el principal y luego el nodo secundario derecho. Los recorridos InOrder proceden a través del subárbol más a la izquierda y terminan en el subárbol más a la derecha. Este tipo de recorrido produce datos organizados en orden ascendente.
Aquí está el ejemplo de recorrido inOrder para el árbol anterior: D > B > E > A > F > C > G
Y aquí está el algoritmo inOrder:
Algoritmo para el inOrder Traversal de una estructura de árbol.
©”TNGD”.com
3. Recorrido posterior al pedido
Este tercer tipo de recorrido primero en profundidad visita el nodo secundario izquierdo, luego el nodo secundario derecho y luego el principal. Con el recorrido del árbol posterior al pedido, todos los subárboles se visitan primero (desde la parte inferior izquierda) y la raíz se visita en último lugar. El recorrido PostOrder es una forma eficiente de eliminar un árbol.
Aquí está el ejemplo de recorrido posterior al pedido para el árbol anterior: D > E > B > F > G > C > A
Y aquí está el algoritmo posterior al pedido:
Algoritmo para el PostOrder Traversal de una estructura de árbol.
©”TNGD”.com
También hay un recorrido transversal que visita los nodos de arriba a abajo y de izquierda a derecha. Esta es la única forma de recorrido primero en anchura.
Redondeando hacia arriba
Como puede ver, los recorridos de árbol hacen la gestión de datos jerárquicos muy simple. Los algoritmos son sencillos y, si se pierde, puede dibujar un árbol básico para orientarse. Estos métodos son tan eficientes que puede construir árboles binarios completos a partir de recorridos anteriores y posteriores al pedido. Practique estos métodos para dominarlos y ampliar su conocimiento.
¿Qué son los recorridos de árbol (en orden, en orden previo y en orden posterior): con ejemplos de preguntas frecuentes (Preguntas frecuentes)
¿Qué es una estructura de datos?
Las estructuras de datos son los formatos específicos que se utilizan para organizar los datos para que puedan almacenarse de forma segura y administrarse y accederse de manera eficiente.
¿Cuáles son los principales tipos de árboles?
Además de los árboles binarios, los principales tipos de árboles incluyen:
Árboles heap Árboles de sintaxis Tries Árboles B Árboles T
¿Qué es un árbol binario perfecto?
Un árbol binario perfecto tiene todos los nodos de hoja a la misma profundidad y todos los nodos principales tienen dos hijos. Esta es otra forma de describir un árbol completamente lleno y sin huecos.
¿Cuáles son ejemplos de estructuras de datos que no son de árbol?
Las estructuras de datos que no son de árbol son principalmente estructuras de datos lineales que incluyen:
Matrices A mapa de bits Matriz Matriz paralela Lista doblemente enlazada Lista autoorganizada
¿Qué son los tipos de datos abstractos?
Los tipos de datos abstractos (ADT) son modelos matemáticos que se pueden usar para estructurar datos y facilitar la programación a gran escala. En informática, los ADT se pueden usar para empaquetar y administrar datos para una variedad de aplicaciones informáticas.