Hay más de una forma de visitar todos los nodos en un BST.
Los árboles binarios son una de las estructuras de datos más utilizadas en programación. Un árbol de búsqueda binaria (BST) permite el almacenamiento de datos en forma de nodos (nodo principal y nodo secundario). nodo) tal que el nodo secundario izquierdo es más pequeño que el nodo principal y el nodo secundario derecho es mayor que.
Los árboles de búsqueda binarios permiten operaciones eficientes de recorrido, búsqueda, eliminación e inserción. En este artículo, aprenderá acerca de las tres formas de recorrer un árbol de búsqueda binaria: recorrido en orden previo, recorrido en orden y recorrido en orden posterior.
Recorrido en orden
El recorrido en orden es el proceso de atravesar nodos de un árbol de búsqueda binaria procesando recursivamente el subárbol izquierdo, luego procesando el nodo raíz y finalmente procesando recursivamente el subárbol derecho. Dado que procesa los nodos en orden de valor ascendente, la técnica se denomina recorrido en orden.
Atravesar es el proceso de visitar cada nodo en una estructura de datos de árbol exactamente una vez.
Algoritmo de recorrido en orden
Repita para atravesar todos los nodos del BST:
- Atraviesa recursivamente el subárbol izquierdo.
- Visite el nodo raíz.
- Atraviesa recursivamente el subárbol derecho.
Visualización de Inorder Traversal
Un ejemplo visual puede ayudar a explicar el recorrido del árbol de búsqueda binaria. Esta figura muestra el recorrido en orden de un árbol de búsqueda binaria de ejemplo:
En este árbol de búsqueda binario, 56 es el nodo raíz. Primero, debe atravesar el subárbol izquierdo 32, luego el nodo raíz 56 y luego el subárbol derecho 62.
Para el subárbol 32, primero recorra el subárbol izquierdo, 28. Este subárbol no tiene hijos, así que a continuación, recorra el nodo 32. A continuación, atraviese el subárbol derecho, 44, que tampoco tiene hijos. Por lo tanto, el orden de recorrido del subárbol con raíz en 32 es 28 -> 32 -> 44.
A continuación, visite el nodo raíz, 56.
Luego, atraviesa el subárbol derecho, enraizado en 62. Comience recorriendo su subárbol izquierdo, enraizado en 58. No tiene hijos, así que visite el nodo 62 a continuación. Finalmente, atraviese el subárbol derecho, 88, que tampoco tiene hijos.
Entonces el algoritmo visita los nodos del árbol en el siguiente orden:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Aplicación de Inorder Traversal
Puede utilizar el recorrido en orden para obtener los valores de los elementos del nodo en orden creciente. Para obtener los valores en orden decreciente, simplemente invierta el proceso: visite el subárbol derecho, luego el nodo raíz y luego el subárbol izquierdo. Puede usar el algoritmo para encontrar la expresión de prefijo de un árbol de expresión.
Recorrido de pedido anticipado
El recorrido en orden previo es similar al inorder, pero procesa el nodo raíz antes de procesar recursivamente el subárbol izquierdo y luego el subárbol derecho.
Algoritmo de Preorder Traversal
Repita para atravesar todos los nodos del BST:
- Visite el nodo raíz.
- Atraviesa recursivamente el subárbol izquierdo.
- Atraviesa recursivamente el subárbol derecho.
Visualización de Preorder Traversal
La siguiente figura muestra el recorrido de preorden del árbol de búsqueda binaria:
En este árbol de búsqueda binaria, comience procesando el nodo raíz, 56. Luego atraviese el subárbol izquierdo, 32, seguido por el subárbol derecho, 62.
Para el subárbol izquierdo, procese el valor en el nodo raíz, 32. A continuación, atraviese el subárbol izquierdo, 28, y finalmente el subárbol derecho, 44. Esto completa el recorrido del subárbol izquierdo enraizado en 32. El recorrido ocurre en el siguiente orden: 56 -> 32 -> 28 -> 44.
Para el subárbol derecho, procese el valor en el nodo raíz, 62. A continuación, atraviese el subárbol izquierdo, 58, y finalmente el subárbol derecho, 88. Nuevamente, ninguno de los nodos tiene hijos, por lo que el recorrido está completo en este punto.
Ha recorrido el árbol completo en el siguiente orden:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Aplicación de Preorder Traversal
Puede usar el recorrido de preorden para crear una copia del árbol más fácilmente.
Recorrido posterior al pedido
El recorrido posterior al orden es el proceso de atravesar los nodos de un árbol de búsqueda binario recursivamente procesando el subárbol izquierdo, luego procesando recursivamente el subárbol derecho y finalmente procesando el nodo raíz. Dado que procesa el nodo raíz después de ambos subárboles, este método se denomina recorrido posterior al orden.
Algoritmo de Postorder Traversal
Repita para atravesar todos los nodos del BST:
- Atraviesa recursivamente el subárbol izquierdo.
- Atraviesa recursivamente el subárbol derecho.
- Visite el nodo raíz.
Visualización de Postorder Traversal
La siguiente figura muestra el recorrido posterior al orden del árbol de búsqueda binaria:
Comience recorriendo el subárbol izquierdo, 32, luego el subárbol derecho, 62. Termine procesando el nodo raíz, 56.
Para procesar el subárbol, con raíz en 32, recorra su subárbol izquierdo, 28. Como 28 no tiene hijos, muévase al subárbol derecho, 44. Proceso 44 ya que tampoco tiene hijos. Por último, procese el nodo raíz, 32. Ha atravesado este subárbol en el orden 28 -> 44 -> 32.
Procese el subárbol derecho usando el mismo enfoque para visitar los nodos en el orden 58 -> 88 → 62.
Finalmente, procese el nodo raíz, 56. Recorrerás el árbol completo en este orden:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Aplicación de Postorder Traversal
Puede usar el recorrido posorden para eliminar un árbol desde la hoja hasta la raíz. También puede usarlo para encontrar la expresión de sufijo de un árbol de expresión.
Para visitar todos los nodos hoja de un determinado nodo antes de visitar el nodo en sí, puede utilizar la técnica transversal posorden.
Complejidad de tiempo y espacio de los recorridos del árbol de búsqueda binaria
La complejidad temporal de las tres técnicas transversales es En), dónde norte es el tamaño de la árbol binario. La complejidad espacial de todas las técnicas transversales es Oh), dónde h es la altura del árbol binario.
El tamaño del árbol binario es igual al número de nodos en ese árbol. La altura del árbol binario es el número de aristas entre el nodo raíz del árbol y su nodo hoja más alejado.
Código de Python para el recorrido del árbol de búsqueda binaria
A continuación se muestra un programa de Python para realizar los tres recorridos del árbol de búsqueda binaria:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(root):
if root:
# Traverse left subtree
inorder(root.left)# Traverse root
print(str(root.value) + ", ", end='')# Traverse right subtree
inorder(root.right)# Function to perform the postorder tree traversal
defpostorder(root):
if root:
# Traverse left subtree
postorder(root.left)# Traverse right subtree
postorder(root.right)# Traverse root
print(str(root.value) + ", ", end='')# Function to perform the preorder tree traversal
defpreorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')# Traverse left subtree
preorder(root.left)# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Este programa debe producir la siguiente salida:
Algoritmos imprescindibles para programadores
Los algoritmos son una parte esencial del viaje de cada programador. Es crucial para un programador estar bien versado en algoritmos. Debe estar familiarizado con algunos de los algoritmos como la ordenación por fusión, la ordenación rápida, la búsqueda binaria, la búsqueda lineal, la búsqueda en profundidad, etc.
