Блог

Главная - Вопросы по программированию - Как создать сбалансированное дерево из списка кортежей

Как создать сбалансированное дерево из списка кортежей

#python

Вопрос:

у меня есть список кортежей в формате [(«A»,1),(«B»,2)……], я хочу создать сбалансированное двоичное дерево на основе целочисленных значений. я попытался сделать что-то вроде приведенного ниже кода, но получил ошибку рекурсии: превышена максимальная глубина рекурсии

 def createBalancedTreeFromSortedArray(self,arr):
      arr = [("A",1),("B",2),("C",3),("D",4),("E",5)]
      sortedarr = sorted(arr, key=lambda x: x[-1])
      mid = len(sortedarr)//2
      newroot= Node(sortedarr[mid][0],sortedarr[mid][1])
      newroot.left= self.createBalancedTreeFromSortedArray(sortedarr[:mid -1])
      newroot.right= self.createBalancedTreeFromSortedArray(sortedarr[mid  1:])
      return newroot

Комментарии:

1. arr = [("A",1),("B",2),("C",3),("D",4),("E",5)] не должно быть внутри функции, это первая ошибка, которую я вижу

2. Для рекурсии вы должны включить «конец случая рекурсии», например, если len(arr)==1 …. сделайте что-нибудь простое…

Метки: