Python - Árbol binario

El árbol representa los nodos conectados por bordes. Es una estructura de datos no lineal. Tiene las siguientes propiedades.

• Un nodo está marcado como nodo raíz.
• Cada nodo que no sea la raíz está asociado con un nodo principal.
• Cada nodo puede tener un número arbiatry de nodo chid.

Creamos una estructura de datos de árbol en Python utilizando el concepto de nodo os discutido anteriormente. Designamos un nodo como nodo raíz y luego agregamos más nodos como nodos secundarios. A continuación se muestra el programa para crear el nodo raíz.

Crear raíz

Simplemente creamos una clase Node y agregamos asignar un valor al nodo. Esto se convierte en un árbol con solo un nodo raíz.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Cuando se ejecuta el código anterior, produce el siguiente resultado:

10

Insertar en un árbol

Para insertar en un árbol usamos la misma clase de nodo creada anteriormente y le agregamos un método de inserción. El método de inserción compara el valor del nodo con el nodo principal y decide agregarlo como un nodo izquierdo o un nodo derecho. Finalmente, el método PrintTree se usa para imprimir el árbol.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Cuando se ejecuta el código anterior, produce el siguiente resultado:

3 6 12 14

Atravesando un árbol

El árbol se puede atravesar decidiendo una secuencia para visitar cada nodo. Como podemos ver claramente, podemos comenzar en un nodo y luego visitar el subárbol izquierdo primero y el subárbol derecho a continuación. O también podemos visitar el subárbol derecho primero y el subárbol izquierdo a continuación. En consecuencia, existen diferentes nombres para estos métodos de recorrido de árbol. Los estudiamos en detalle en el capítulo que implementa los algoritmos de recorrido de árbol aquí. Algoritmos de recorrido de árbol