Recorrido en orden de un árbol en Python

1. Recorrido en orden de un árbol
2. Implementación transversal de árbol en orden en Python

Un árbol es una estructura de datos jerárquica que consta de nodos conectados por bordes. Atravesar un árbol significa visitar cada nodo del árbol exactamente una vez.

Recorremos el árbol para diferentes propósitos, como mostrar los nodos, encontrar el nodo más grande y el más pequeño, buscar, ordenar, etc. En este artículo, aprenderemos e implementaremos el recorrido inorder de un árbol en Python.

Recorrido en orden de un árbol

El recorrido en orden es un tipo de recorrido primero en profundidad. Supongamos que tenemos el siguiente árbol.

Si aplicamos el recorrido inorder, seguiremos los siguientes pasos para cada nodo.

1. Primero, debemos visitar todos los nodos del subárbol izquierdo.
2. Luego, visitamos el nodo padre.
3. Luego, visitamos todos los nodos en el subárbol derecho.

Obtendremos los nodos en el orden 4, 2, 5, 1, 6, 3, 7.

Implementación transversal de árbol en orden en Python

Hay dos formas de implementar el recorrido inorder en Python. El enfoque recursivo e iterativo.

Enfoque recursivo

El enfoque recursivo es fácil de implementar y comprender. En el siguiente código, hemos creado una clase Node como estructura de datos para almacenar el árbol.

Cada nodo consta de un valor, su hijo izquierdo y derecho. El recorrido inorder funcionará recursivamente para los subárboles izquierdo y derecho.

Para cada nodo, el recorrido inorder se realizará visitando su nodo izquierdo, el padre y el nodo derecho.

Código de ejemplo:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.val))
        inorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Producción :

Inorder traversal of the Tree
4
2
5
1
6
3
7

Enfoque iterativo

En un enfoque iterativo, debemos mantener una pila para almacenar los nodos que visitaremos más adelante. Creamos la clase Node en el siguiente código, al igual que antes.

Hemos creado una pila vacía y comenzamos desde el nodo raíz convirtiéndolo en el nodo actual. Si el nodo actual existe, lo empujaremos a la pila e iremos a su nodo izquierdo.

De lo contrario, si el nodo no existe, sacaremos un elemento de la pila y lo imprimiremos. Cuando no exista un nodo izquierdo, iremos al nodo derecho convirtiéndolo en el nodo actual.

Repetiremos el mismo procedimiento iterativamente hasta que tanto la pila como el elemento actual estén vacíos.

Código de ejemplo:

from collections import deque


class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    stack = deque()
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            print(curr.val)
            curr = curr.right


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Producción :

Inorder traversal of the Tree
4
2
5
1
6
3
7