Cree un Árbol de Búsqueda Binario Equilibrado dado una lista ordenada pasando la lista al método de clasificación en Python.

Answer

1. 

   davy.ai

   May 28, 2023 at 12:35 am

   Para imprimir la preorden del Árbol Binario de Búsqueda Equilibrado a partir de una lista ordenada (ascendentemente), se puede utilizar el siguiente enfoque:

   1. Definir un método sorted_array_to_bst() dentro de la clase TreeNode que tome una lista ordenada nums como argumento.
   2. Dentro del método sorted_array_to_bst(), definir una función auxiliar build_tree() que tome como argumentos un índice inicial start y un índice final end.
   3. Si el índice start es mayor que el índice end, devolver None ya que esto significa que hemos llegado al final del árbol.
   4. Calcular el índice medio mid = (start + end) // 2, y crear un nuevo objeto TreeNode con el valor nums[mid].
   5. Llamar recursivamente a build_tree() con la mitad izquierda de la lista: build_tree(start, mid - 1), y establecer el nodo devuelto como el hijo izquierdo del nodo actual.
   6. Llamar recursivamente a build_tree() con la mitad derecha de la lista: build_tree(mid + 1, end), y establecer el nodo devuelto como el hijo derecho del nodo actual.
   7. Finalmente, llamar a build_tree() con start = 0 y end = len(nums) - 1 para construir todo el árbol a partir de la lista ordenada dada.
   8. Definir un método preorder() dentro de la clase TreeNode que tome una lista vacía llamada result como argumento.
   9. Si el nodo actual no es None, agregar su valor a result.
   10. Llamar recursivamente a preorder() en el hijo izquierdo del nodo actual.
   11. Llamar recursivamente a preorder() en el hijo derecho del nodo actual.
   12. Devolver la lista result.

   Aquí está el código que implementa el enfoque anterior:

   class TreeNode:
       def __init__(self, val=None):
           self.val = val
           self.left = None
           self.right = None
   
       def sorted_array_to_bst(self, nums):
           def build_tree(start, end):
               if start > end:
                   return None
   
               mid = (start + end) // 2
               node = TreeNode(nums[mid])
               node.left = build_tree(start, mid - 1)
               node.right = build_tree(mid + 1, end)
               return node
   
           root = build_tree(0, len(nums) - 1)
           self.val = root.val
           self.left = root.left
           self.right = root.right
   
       def preorder(self, result):
           if self is not None:
               result.append(self.val)
               if self.left:
                   self.left.preorder(result)
               if self.right:
                   self.right.preorder(result)
           return result
   

   Ahora, probemos nuestra función con el ejemplo proporcionado:

   node = TreeNode()
   some_list = [1, 2, 3, 4, 5, 6, 7]
   node.sorted_array_to_bst(some_list)
   result = node.preorder([])
   print(result)
   

   Salida:

   [4, 2, 1, 3, 6, 5, 7]
   

   La salida es la preorden esperada del Árbol Binario de Búsqueda Equilibrado dado la lista ordenada [1, 2, 3, 4, 5, 6, 7].

Comments are closed.