Дерево AVL: проблема наследования Python

У меня есть классы деревьев: BinarySearchTree, TreeNode и AVLTree.

Класс TreeNode используется в классе BinarySearchTree. AVLTree наследует BinarySearchTree. См. код ниже:

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

Класс узла дерева выглядит следующим образом:

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:

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, я получаю эту ошибку: 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


python tree avl-tree binary-search-tree
person koseph    schedule 02.09.2015    source источник
comment
Почему вы вызываете TreeNode.__init__ в своем методе AVLTree.__init__, если вы вообще не наследуете от TreeNode?   -  person Blckknght    schedule 02.09.2015

Ответы (2)


arrow_upward
0
arrow_downward

Просмотрев текст, над которым вы работаете, я думаю, что вижу, где вы запутались. Переход от классов BinarySearchTree к классам AVLTree требует, чтобы класс TreeNode также был обновлен (или, возможно, был создан новый класс AVLTreeNode) с новым атрибутом balanceFactor. Это никогда специально не описывается в тексте, и поэтому вы начали объединять новые вещи, которые нужны узлу, в класс Tree там, где это неуместно.

Вместо этого поместите материал balanceFactor в соответствующий класс Node:

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, когда он ему понадобится.

person Blckknght    schedule 02.09.2015

arrow_upward
1
arrow_downward

Я не совсем уверен, что полностью понял ваш код, но мне кажется, что ваша проблема (или по крайней мере одна из ваших проблем) заключается в этой строке TreeNode.__init__(self,key,val,left,right,parent).

Бьюсь об заклад, вы не хотите передавать параметр self, так как он имеет тип AVLTree, а интерпретатор ожидает тип TreeNode. Теперь я думаю, что вы, возможно, захотите сделать в конструкторе AVLTree просто создать объект TreeNode, который будет вашим корневым узлом AVL. Чтобы создать экземпляр класса в Python, вам не нужно явно вызывать метод __init__. Вы можете просто сделать class_instance = Class(parameters) или, в вашем случае, self.root = TreeNode(key, val, left, right, parent).

Итак, мы можем превратить то, что вы разместили, в это: (я покажу только то, что я изменил, остальные классы мне показались хорошими)

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")
person jpleitao    schedule 02.09.2015
comment
я сделал это, и он все еще возвращает ту же ошибку. Но я могу решить ее сейчас. Где-то было несколько ошибок. - person koseph; 02.09.2015