AVL 树：Python 继承问题

Question

我有树 classes：BinarySearchTree、TreeNode 和 AVLTree。

BinarySearchTree class 中使用了 TreeNode class。 AVLTree继承了BinarySearchTree.See下面的代码：

from Tnode import TreeNode
  class BinarySearchTree:
         def __init__(self):
             self.root = None
             self.size = 0

树节点 class 如下所示：

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

AVLTree Class:

from  Tnode import TreeNode
from binstree import BinarySearchTree

class AVLTree(BinarySearchTree):
    def __init__(self,key,val,left=None,right=None,parent=None,balanceFactor=0):
        TreeNode.__init__(self,key,val,left,right,parent)
        self.balanceFactor = balanceFactor     
        self.root = None
        self.size = 0

每当我运行 AVLTree class 我得到这个错误：AttributeError: TreeNode instance has no attribute 'balanceFactor'

我做错了什么？代码可以在这里查看： http://interactivepython.org/runestone/static/pythonds/Trees/AVLTreeImplementation.html

http://interactivepython.org/runestone/static/pythonds/Trees/SearchTreeImplementation.html

Answer 1

我不完全确定我完全理解你的代码，但在我看来你的问题（或至少你的问题之一）在这一行 TreeNode.__init__(self,key,val,left,right,parent).

我打赌你不想传递 self 参数，因为它是 AVLTree 类型，而解释器需要 TreeNode 类型。现在我认为您可能想在 AVLTree 构造函数中做的是简单地创建一个 TreeNode 对象作为您的 AVL 根节点。要在 Python 中创建 class 的实例，您不需要显式调用 __init__ 方法。你可以简单地做 class_instance = Class(parameters)，或者在你的情况下 self.root = TreeNode(key, val, left, right, parent).

所以，我们可以将您发布的内容变成这样：（我只会展示我更改的内容，classes 的其余部分对我来说似乎没问题）

class AVLTree(BinarySearchTree):
def __init__(self, key, val, left=None, right=None, parent=None, balancefactor=0):
    self.balanceFactor = balancefactor
    self.root = TreeNode(key, val, left, right, parent)
    self.size = 1

我们正在使用传递给树构造函数的信息来创建根节点并更新树的大小。您可以创建一个带有根节点的简单 AVL 树，没有大问题：

if __name__ == '__main__':
     avl = AVLTree("key", "val")

Answer 2

查看了您正在处理的文本后，我想我明白您在哪里感到困惑了。从 BinarySearchTree 到 AVLTree classes 的变化要求 TreeNode class 也被更新（或者可能是一个新的 AVLTreeNode class 被创建）与一个新的 balanceFactor 属性。这在文本中从未具体描述过，因此您已经开始将节点需要的新内容合并到不合适的 Tree class 中。

相反，将 balanceFactor 内容放入适当的 Node class:

class AVLTreeNode(TreeNode):
    def __init__(self,key,val,left=None,right=None,parent=None,balanceFactor=0):
        TreeNode.__init__(self,key,val,left,right,parent)
        self.balanceFactor = balanceFactor

现在您的 AVLTree 代码只需要创建 AVLTreeNode 个对象而不是 TreeNode 个对象，它会在需要时找到合适的 balanceFactor 属性。

AVL 树：Python 继承问题

AVL tree: Python inheritance issue

python

tree

avl-tree

binary-search-tree