Dado un árbol binario, escriba una solución iterativa y recursiva para recorrer el árbol utilizando el recorrido de orden en C++, Java y Python.
A diferencia de las listas enlazadas, las matrices unidimensionales y otras estructuras de datos lineales, que se recorren en orden lineal, los árboles pueden ser recorridos de múltiples maneras en orden de profundidad (preorden, inorden y postorden) o en orden de amplitud (recorrido por orden de nivel). Más allá de estos recorridos básicos, son posibles varios esquemas más complejos o híbridos, como las búsquedas limitadas en profundidad, como la búsqueda iterativa en profundidad. En este post, se discute en detalle el recorrido de árboles en orden.
El recorrido de un árbol implica iterar sobre todos los nodos de alguna manera. Como el árbol no es una estructura de datos lineal, puede haber más de un posible nodo siguiente desde un nodo dado, por lo que algunos nodos deben ser diferidos, es decir, almacenados de alguna manera para ser visitados posteriormente. El recorrido puede hacerse de forma iterativa donde los nodos diferidos se almacenan en la pila, o puede hacerse por recursión, donde los nodos diferidos se almacenan implícitamente en la pila de llamadas.
Para recorrer un árbol binario (no vacío) de forma inordenada, debemos hacer estas tres cosas para cada nodo n empezando por la raíz del árbol:
(L) Recorrer recursivamente su subárbol izquierdo. Cuando este paso termina, volvemos a n.(N) Procesa el propio n.(R) Recorre recursivamente su subárbol derecho. Cuando este paso ha terminado, estamos de vuelta en n de nuevo.En el recorrido normal del orden, visitamos el subárbol izquierdo antes del subárbol derecho. Si visitamos el subárbol de la derecha antes de visitar el subárbol de la izquierda, se denomina recorrido en orden inverso.
Como podemos ver, antes de procesar cualquier nodo, se procesa primero el subárbol de la izquierda, seguido del nodo, y al final se procesa el subárbol de la derecha. Estas operaciones pueden definirse recursivamente para cada nodo. La implementación recursiva se denomina búsqueda en profundidad (DFS), ya que el árbol de búsqueda se profundiza tanto como sea posible en cada hijo antes de ir al siguiente hermano.
A continuación se muestra el programa en C++, Java y Python que lo demuestra:
Implementación iterativa –
Para convertir el procedimiento recursivo anterior en uno iterativo, necesitamos una pila explícita. A continuación se muestra un sencillo algoritmo iterativo basado en la pila para realizar el recorrido en orden.
iterativoInorder(nodo)
El algoritmo puede implementarse como sigue en C++, Java y Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Iterativo función para realizar el recorrido en orden en el árbol
void inorderIterative(Node *root)
{
// crear una pila vacía
stack<Node*> stack; ¡
// empezar desde el nodo raíz (establecer el nodo actual al nodo raíz)
Nodo *curr = raíz;
// si el nodo actual es nulo y la pila también está vacía, hemos terminado
while (!stack.empty() || curr != nullptr)
{
// si el nodo actual existe, empujarlo a la pila (diferirlo)
// y pasar a su hijo izquierdo
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
curr = stack.top();
stack.pop();
cout << curr->data << » «;
curr = curr->right;
}
}
}
|
Descargar código completo
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Iterativo función para realizar un recorrido inordenado en el árbol
public static void inorderIterative(TreeNode root)
{
// crear una pila vacía
Stack<TreeNode> stack = new Stack(); ¡
// empezar desde el nodo raíz (establecer el nodo actual al nodo raíz)
TreeNode curr = raíz;
// si el nodo actual es nulo y la pila también está vacía, hemos terminado
while (!stack.empty() || curr != null)
{
// si el nodo actual existe, empujarlo a la pila (diferirlo)
// y pasar a su hijo izquierdo
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
curr = stack.pop();
System.out.print(curr.data + » «);
curr = curr.right;
}
}
}
|
Descarga el código completo
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Función iterativa para realizar un recorrido de orden en el árbol
def inorderIterative(root):
# crear una pila vacía
pila = deque()
# empezar desde el nodo raíz (poner el nodo actual en el nodo raíz)
curr = raíz
# si el nodo actual es Ninguno y la pila también está vacía, hemos terminado
while stack or curr:
# si el nodo actual existe, lo empujamos a la pila (lo diferimos)
# y nos movemos a su hijo izquierdo
si curr:
stack.append(curr)
curr = curr.left
else:
# de lo contrario, si el nodo actual es None, pop un elemento de la pila,
# imprimirlo, y finalmente establecer el nodo actual a su hijo derecho
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Descarga el código completo de la ejecución
La complejidad temporal de las soluciones anteriores es O(n), donde n es el número total de nodos del árbol binario. La complejidad espacial del programa es O(n) ya que el espacio requerido es proporcional a la altura del árbol, que puede ser igual al número total de nodos del árbol en el peor de los casos para árboles sesgados.