Mi blog guia del deporte

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

• Un nodo se marca como nodo raíz.

• Cada nodo no raíz está asociado con un nodo padre.

• Cada nodo puede tener cualquier número de hijos de nodo.

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

crear raíz

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

ejemplo

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()

producción

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

10

Pegar en un árbol

Para insertar en un árbol, usaremos la misma clase de nodo que creamos anteriormente y le agregaremos una clase de inserción. La clase de inserción compara el valor del nodo con el nodo principal y decide si agregarlo como nodo izquierdo o derecho. Finalmente, la clase PrintTree se usa para imprimir el árbol.

ejemplo

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()

producción

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

3 6 12 14

atravesar un arbol

El árbol se puede recorrer estableciendo una secuencia para visitar cada nodo. Como podemos ver claramente, podemos comenzar en un nodo y luego visitar primero el subárbol izquierdo y luego el subárbol derecho. O también podemos visitar primero el subárbol derecho y luego el subárbol izquierdo. En consecuencia, existen diferentes nombres para estos métodos de recorrido de árboles.

Algoritmos de recorrido de árboles

Traversal es un proceso para visitar todos los nodos en un árbol e imprimir también sus valores. Dado que todos los nodos están conectados por bordes (enlaces), siempre comenzamos en el nodo raíz (nodo principal). Es decir, no podemos acceder aleatoriamente a un nodo en un árbol. Hay tres formas de atravesar un árbol.

Gira bien

Con este método transversal, primero se visita el subárbol izquierdo, luego la raíz y luego el subárbol derecho. Siempre debemos recordar que cada nodo puede representar en sí mismo un subárbol.

En el siguiente programa de Python, usamos la clase Node para crear marcadores de posición para los nodos raíz, izquierdo y derecho. A continuación, creamos una función de inserción para agregar datos al árbol. Finalmente, la lógica transversal en orden se implementa creando una lista vacía y agregando primero el nodo izquierdo, seguido del nodo raíz o principal.

Por último, se agrega el nodo izquierdo para completar el recorrido en orden. Tenga en cuenta que este proceso se repite para cada subárbol hasta que se recorren todos los nodos.

ejemplo

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         else 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()
# Inorder traversal
# Left -> Root -> Right
   def inorderTraversal(self, root):
      res = []
      if root:
         res = self.inorderTraversal(root.left)
         res.append(root.data)
         res = res + self.inorderTraversal(root.right)
      return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))      

producción

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

[10, 14, 19, 27, 31, 35, 42]

Reservar Traversal

Con este método transversal, primero se visita el nodo raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.

En el siguiente programa de Python, usamos la clase Node para crear marcadores de posición para el nodo…