Отладка Python: бинарное дерево поиска (ошибка объектов)

Question

Итак, я получил небольшую ошибку в этой программе, но я действительно не мог понять, как ее исправить, и я был бы очень признателен, если бы кто-то мог помочь мне указать, где она находится.По сути, первая функция преобразует отсортированный массив в сбалансированное двоичное дерево поиска, а вторая функция возвращает высоту дерева от заданного узла.Когда я скомпилировал программу, я получил такую ​​ошибку:

Я попытался распечатать объект "aNode" для тестирования, и я был удивлен, обнаружив, что сначала онуказывал на объект Node, но затем указывал на объект Tree (?), который меня сильно смутил, и я действительно не знаю, как это отладить.Большое спасибо за любую помощь.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self):
        self.root = None
    # create a balanced binary search tree from a sorted list
    def create_tree (self, a_list):
       if (len(a_list) <= 0): return None
       mid = (len(a_list))//2 # find the mid value of the sorted array & make it root
       self.root = Node(a_list[mid])
       self.root.lChild = self.create_tree(a_list[:mid])
       self.root.rChild = self.create_tree(a_list[mid+1:])
       return self

    def get_height (self, aNode):
       if (aNode == None):
          return -1
       else:
          print(aNode) # I DID MY TEST HERE WHERE IT FIRST PRINT "NODE OBJECT", BUT PRINT "TREE OBJECT" LATER AND CAUSE THE PROGRAM TO FAIL
          rHeight = self.get_height(aNode.rChild)
          lHeight = self.get_height(aNode.lChild)
          return (1+rHeight) if rHeight > lHeight else (1+lHeight)

def main():
    new_tree = Tree().create_tree([1,9,11,17])
    new_tree.get_height(new_tree.root)
 main()

Большое спасибо!

Answer 1

Проблема в том, что вы переопределяете self.root новым узлом каждый раз. Таким образом, на каждом уровне ниже в рекурсивных вызовах вы сбрасываете self.root объекта Tree с новым пустым узлом.

Некоторые незначительные изменения в вашем коде должны решить проблему. Также добавлен print в вызов get_height () в main, поскольку он просто возвращает целое число, и вы никому его не назначаете.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lChild = None
        self.rChild = None

class Tree(object):
    def __init__(self, a_list):
        self.root = self.create_tree(a_list)

    # create a balanced binary search tree from a sorted list
    def create_tree (self, a_list):
       if (len(a_list) <= 0): return None
       mid = (len(a_list))//2 
       root = Node(a_list[mid])
       root.lChild = self.create_tree(a_list[:mid])
       root.rChild = self.create_tree(a_list[mid+1:])
       return root

    def get_height (self, aNode):
       if (aNode == None):
          return -1
       else:
          print(aNode) 
          rHeight = self.get_height(aNode.rChild)
          lHeight = self.get_height(aNode.lChild)
          return (1+rHeight) if rHeight > lHeight else (1+lHeight)

def main():
    new_tree = Tree([1,9,11,17])
    print(new_tree.get_height(new_tree.root))