调试 Python：二进制搜索树（对象错误）

Question

所以我在这个程序中遇到了一个小错误，但我真的不知道如何修复它，如果有人能帮我指出它在哪里，我将不胜感激。所以基本上，第一个函数将排序数组转换为平衡二叉搜索树，第二个函数 returns 从给定节点开始树的高度。当我编译程序时，我得到了这样的错误：

我试图打印出"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。因此，递归调用中的每个级别，您都在用一个新的空节点重置 Tree 对象的 self.root。

对您的代码进行一些小改动应该可以解决该问题。还向 main 中的 get_height() 调用添加了打印，因为它只是 returns 一个整数，您没有将其分配给任何东西。

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

调试 Python：二进制搜索树（对象错误）

Debug Python: Binary Search Tree (Objects bug)

python

binary-tree

object