Imprimir árbol binario en Python

1. Árbol binario en Python
2. Orden transversal de un árbol
3. Implementación de árbol binario en Python
4. Imprima todo el árbol binario usando Python

Este artículo discutirá un árbol binario y cómo podemos usarlo. También veremos cómo podemos imprimirlo usando Python.

Aprenderemos sobre las terminologías utilizadas al trabajar con árboles binarios. También veremos un ejemplo de un árbol binario usando código Python.

Árbol binario en Python

Los árboles binarios de Python son una de las estructuras de datos más eficientes disponibles y también son relativamente simples de implementar. Un árbol binario es una estructura de datos similar a un árbol con un nodo raíz y dos nodos secundarios, uno izquierdo y otro derecho.

Cada nodo puede tener cualquier número de nodos secundarios. Este artículo verá cómo crear y atravesar un árbol binario en Python.

Comprendamos mejor la terminología asociada con el árbol.

1. Raíz: El nodo superior de un árbol sin padre. Cada árbol tiene una raíz.
2. Edge: Edge es un enlace padre-hijo.
3. Hoja: Un nodo sin hijos. El nodo final del árbol. Los árboles tienen múltiples nudos de hojas.
4. Subárbol: El árbol utiliza un nodo como raíz.
5. Profundidad: La profundidad es la distancia del nodo a la raíz.
6. Altura: la altura del nodo es la distancia al nodo más profundo del subárbol.
7. Altura del Árbol: La altura del árbol es el nodo más alto y corresponde a la misma altura que el nodo raíz.

Orden transversal de un árbol

El árbol se recorre comenzando en el nodo raíz y visitando los nodos secundarios izquierdo y derecho. El orden en que se visitan los nodos se denomina orden transversal.

Árbol transversal en orden

Hay varias formas diferentes de recorrer un árbol binario. El más común es el recorrido en orden, que visita los nodos secundarios izquierdo, raíz y derecho.

Reservar árbol transversal

Otro recorrido estándar es el recorrido de pedido previo, que visita primero el nodo raíz, luego el hijo izquierdo y finalmente el hijo derecho.

El recorrido en orden es la forma más eficiente de visitar todos los nodos en un árbol binario, ya que visita cada nodo solo una vez. El recorrido de pedido previo es un poco menos eficiente ya que llama al nodo raíz dos veces.

Sin embargo, el recorrido de orden anticipado se usa a menudo cuando queremos modificar el árbol durante el recorrido, ya que es fácil modificar primero el nodo raíz y luego los nodos secundarios izquierdo y derecho.

Aquí hay una sintaxis y una implementación simple de el recorrido en orden en Python.

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.val)
        inorder(node.right)

Entonces, así es como codificamos cuando queremos usar el método transversal en orden.

Y aquí está el recorrido de pre-pedido:

def preorder(node):
    if node is not None:
        print(node.val)
        preorder(node.left)
        preorder(node.right)

Recorrido posterior al pedido

También podemos atravesar el árbol en orden posterior, que visita el hijo izquierdo, el hijo derecho y luego el nodo raíz. Sin embargo, el recorrido posterior al pedido es menos común ya que es menos eficiente que los otros dos recorridos.

Hay otras formas de recorrer un árbol binario, como el recorrido por orden de niveles, que visita los nodos del árbol nivel por nivel. Sin embargo, no cubriremos ese recorrido en este artículo.

Ahora que hemos visto cómo atravesar un árbol binario, veamos cómo crear un árbol binario e imprimirlo usando Python.

Implementación de árbol binario en Python

Sabemos qué es un árbol binario y la terminología relacionada con él. Implementaremos el árbol binario usando Python para comprender mejor cómo funciona el árbol binario.

Todo lo que tenemos que hacer es copiar ese código aquí y escribir un nuevo código en él. Como es parte del árbol binario, debemos escribir el nuevo código con los códigos ya escritos.

Código de ejemplo:

class binaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def printTree(root):
        print(root.data)
        print("L", root.left.data, end=": ")
        print("R", root.right.data, end=": ")


bnt1 = binaryTreeNode(1)
bnt2 = binaryTreeNode(2)
bnt3 = binaryTreeNode(3)
bnt1.left = bnt2
bnt1.right = bnt3
bnt2.left = bnt1
bnt2.right = bnt3
bnt3.left = bnt1
bnt3.right = bnt2

El método def printTree(root) nos da la raíz. Porque cuando tenemos la raíz del árbol, podemos acceder a todo el árbol con los nodos.

Después de declarar el método, comprobaremos algunas condiciones. Podemos ver el método def PrintTree(root) en el código de arriba.

Intentemos imprimir la raíz 1, bnt1, para ver qué obtenemos.

Código de ejemplo:

print(bnt1.printTree())

Producción :

1
L 2: R 3: None

El resultado muestra que el árbol contiene dos nodos (el nodo izquierdo y el nodo derecho). El dato en el nodo izquierdo es 2, y en el nodo derecho es 3.

También podemos imprimir bnt2 y bnt3 para ver qué puntos de datos contienen.

Imprima todo el árbol binario usando Python

Aquí está todo el árbol binario. Podemos ejecutarlo y aprender más sobre cómo se imprime un árbol binario usando Python con la biblioteca aleatoria de Python.

import random


class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None

    def insert(self, key):
        if self.key == key:
            return
        elif self.key < key:
            if self.right is None:
                self.right = BinaryTree(key)
            else:
                self.right.insert(key)
        else:  # self.key > key
            if self.left is None:
                self.left = BinaryTree(key)
            else:
                self.left.insert(key)

    def display(self):
        lines, *_ = self._display_aux()
        for line in lines:
            print(line)

    def _display_aux(self):
        """Returns list of strings, width, height, and horizontal coordinate of the root."""
        # No child.
        if self.right is None and self.left is None:
            line = "%s" % self.key
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle
        # Only left child.
        if self.right is None:
            lines, n, p, x = self.left._display_aux()
            s = "%s" % self.key
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
        # Only right child.
        if self.left is None:
            lines, n, p, x = self.right._display_aux()
            s = "%s" % self.key
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
        # Two children.
        left, n, p, x = self.left._display_aux()
        right, m, q, y = self.right._display_aux()
        s = "%s" % self.key
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
        second_line = (
            x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        )
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2


b = BinaryTree(100)
for _ in range(100):
    b.insert(random.randint(50, 150))
b.display()

Producción:

La salida del código sigue cambiando cada vez que lo ejecutamos. Esto se debe a que estamos usando el módulo aleatorio de Python.

Esperamos que este artículo le resulte útil para comprender cómo imprimir un árbol binario usando Python.