OOP Python：尝试创建二叉搜索树，获取 'attributeError' 对象变态
OOP Python: Trying to create Binary Search Tree, gets 'attributeError' obeject gets perverted
我正在尝试创建一个随机二叉搜索树。我正在按照此 web page 上的说明（伪代码）进行操作。此外，我正在使用 TEAP（树堆）技术为元素提供不同的优先级，从而制作平衡的二叉搜索树。
代码如下：
import random
class TreapNode:
"""Skapar en nod för det randomiserade binära sökträdet"""
def __init__(self, value = None, parent = None, left_child = None, right_child = None):
self.val = value
self.pri = random.randint(-1000, 1000)
self.par = parent
self.left = left_child
self.right = right_child
def addParent(self, p):
"""Tilldelar noden en förälder"""
self.par = p
def addLeft(self, lc):
"""Tilldelar noden ett barn till vänster"""
self.left = lc
def addRight(self, rc):
"""Tilldelar noden ett barn till höger"""
self.right = rc
def addValue(self, val):
"""Tilldelar noden ett värde, en s.k. adress"""
self.val = val
def getParent(self):
"""Returnerar nodens förälder"""
return self.par
def getLeft(self):
"""Returnerar nodens vänstra barn"""
return self.left
def getRight(self):
"""Returnerar nodens högra barn"""
return self.right
def getValue(self):
"""Returnerar nodens värde/adress"""
return self.val
def getPriority(self):
"""Returnerar nodens prioritet"""
return self.pri
class BalancedBinaryTree:
"""Skapar ett tomt binärt sökträd som är välbalanserat"""
def __init__(self):
self.root = None
self.size = 0
self.string = []
def rotate_left(self, u): # privat
"""Byter plats på noden u och dess högra barn genom rotation""" #denna algoritm bevarar
w = u.getRight() #"binära-sökträds" egenskapen
w.addParent(u.getParent) #hos varje nod
if w.getParent() != None:
p = w.getParent()
if p.getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addRight(w.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(w)
w.addLeft(u)
if w.getParent() == None:
self.root = w
def rotate_right(self, u): # privat
"""Byter plats på noden u och dess vänstra barn genom rotation""" #denna algoritm bevarar
w = u.getLeft() #"binära-sökträds" egenskapen
w.addParent(u.getParent()) #hos varje nod
if w.getParent() != None:
if w.getParent().getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addLeft(w.getRight())
if u.getLeft() != None:
u.getLeft().addParent(u)
u.addParent(w)
w.addRight(u)
if w.getParent() == None:
self.root = w
def add(self, val):
"""Låter användaren lägga till ett värde, men bara om det inte redan finns"""
u = TreapNode(value = val)
if self.add_node(val, u):
self.bubble_up(u)
self.size += 1
self.string.append(val)
return True
return False
def bubble_up(self, u): # prviat
"""Om prioriteten hos u är lägre än dess förälder, så byter u och föräldern plats"""
while u.getParent() != None and u.getParent().getPriority() > u.getPriority():
if u.getParent().getRight() == u:
self.rotate_left(u.getParent())
else:
self.rotate_right(u.getParent())
if u.getParent() == None:
self.root = u
def findString(self, val):
"""Låter användaren söka efter specifika värden. Returnerar värdet om det finns, annars None"""
w = self.root
while w != None:
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w.getValue()
return None
def add_node(self, val, node): # privat
"""Tilldelar ett löv ett barn med värdet val""" # här bryts inte "binär-
p = self.find_last(val) # sökträds" regeln
return self.add_child(p, node)
def find_last(self, val): #privat
"""Finner lämplig nod som kan tilldelas ett barn till höger/vänster med värdet val"""
w = self.root
prev = None
#if w != None:
# print(w.getValue())
#else:
# print(w)
while w != None:
prev = w
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w
return prev
def add_child(self, p, u): #privat
"""Tilldelar en nod p ett barn u till höger/vänster"""
if p == None:
self.root = u
else:
if u.getValue() < p.getValue():
p.addLeft(u)
u.addParent(p)
elif u.getValue() > p.getValue():
p.addRight(u)
u.addParent(p)
else:
print(u.getValue())
print(p.getValue())
return False
return True
def getSize(self):
return self.size
def orderedString(self):
if self.size == 0:
msg = "[]"
return msg
else:
orderedlist = sorted(self.string)
return orderedlist
def main():
# Testkod till TreapNode() klassen
nod = TreapNode()
nod.addParent(TreapNode(value = "abc", left_child = nod))
assert nod.getParent().getValue() == "abc"
assert nod.getParent().getLeft() == nod
assert -1000 <= nod.getPriority() <= 1000
nod.addRight(TreapNode(value=10, parent=nod))
nod.addValue("abcd")
assert nod.getRight().getValue() == 10
assert nod.getValue() == "abcd"
# Testkod till BalancedBinaryTree
tree = BalancedBinaryTree()
assert tree.orderedString() == "[]"
assert tree.getSize() == 0
assert tree.findString("abc") == None
tree.add("abc")
tree.add("aaa")
tree.add("bbb")
assert tree.orderedString() == ['aaa', 'abc', 'bbb']
assert tree.getSize() == 3
tree.add("hej")
tree.add("min")
tree.add("van")
tree.add("pa")
tree.add("andra")
tree.add("sidan")
tree.add("jorden")
tree.add("omg")
tree.add("lol")
tree.add("sos")
assert tree.orderedString() == ['aaa', 'abc', 'andra', 'bbb', 'hej', 'jorden', 'min', 'pa', 'sidan', 'van']
assert tree.getSize() == 10
tree.add("hej") # finns redan i trädet
assert tree.getSize() == 10 # alltså finns ingen dublett
assert tree.findString("hej") == "hej"
assert tree.findString("jorden") == "jorden"
assert tree.findString("sos") == "sos"
assert tree.findString("aldrig") == None
assert tree.findString("nagonsin") == None
# Tidskomplexitet för alla operationer:
#
# add() = O(nlog(n)) där n är antalet element
# findString() = O(log(n))
# getSize() = O(1)
# orderedString() = O(n), eftersom sorted() måste jämföra n element
if __name__ == "__main__":
main()
现在，当我执行这段代码时，我收到一条错误消息 AttributeError: 'function' object has no attribute 'getLeft'。好的，所以我检查传递给函数的对象，这似乎发生了：
作为节点对象的元素最终被传递给 rotate_left(self,u) 方法。这里的参数u就是nodeobject。我"reach"在这个nodeobject里面得到它的leftchild。然后我又在'reach'这个object内部返回Nodeobject，leftchildobjects就是所谓的parent。现在事情变得混乱了：Parentobject 在某种程度上是变态的。它应该与 Nodeobject 相同，但我看不出我做错了什么。如果我打印 nodeobject 及其 leftchild 和 leftchildParent，您会注意到其中的区别。
节点对象<__main__.TreapNode object at 0x7fcd32c90898>
Leftchildobject <__main__.TreapNode object at 0x7fcd32c908d0>
Leftchildobjects parent（这显然应该是上面的Nodeobject）<bound method TreapNode.getParent of <__main__.TreapNode object at 0x7fcd32c90898>>
最后一步发生了什么？
编辑
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.addParent(u.getRight())
p.addParent(u.getParent)
if p.getParent() != None:
if p.getParent().getLeft() == u:
p.getParent().addLeft(p)
else:
p.getParent().addRight(p)
u.addRight(p.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(p)
p.addLeft(u)
if p.getParent() == None:
self.root = p
这里是有些东西不起作用的方法。 if 语句 if p.getParent().getLeft() == u 引发了一个错误，即 AttributeError: 'function' object has no attribute 'getLeft'。我到底应该怎么做才能不引发此错误，对我来说看起来不错(?)
getParent是一个方法，你必须调用它来获取值。
w.addParent(u.getParent())
值得注意的是，getter/setter 模式在 Python 中并没有真正的意义，如果没有它，您的代码将大大简化。
编辑：
查看第 p.addParent(u.getParent) 行。那里发生的事情是您将 u.getParent 指定为 p 的父级。但是 u.getParent 是一种方法。因此，当您执行 p.getParent().getLeft() 时，这等同于 u.getParent.getLeft()，这不起作用，因为该方法没有 getLeft 方法。
关于 getter 和 setter：是什么让您认为您需要它们？您的方法可以很容易地
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.par = u.right
p.par = u.par # Is this what you intend to happen?
if p.par: # None is falsy
if p.par.left == u:
p.par.left = p
else:
p.par.right = p
u.right = p.left
if u.right:
u.right.par = u
u.par = p
p.left = u
if not p.par:
self.root = p
我也没有在您的对象中看到 __eq__ 方法。默认 __eq__ 方法仅 returns 如果两个对象是同一实例则为真。由于您在代码中使用 ==，这可能不是您想要的。
我正在尝试创建一个随机二叉搜索树。我正在按照此 web page 上的说明（伪代码）进行操作。此外，我正在使用 TEAP（树堆）技术为元素提供不同的优先级，从而制作平衡的二叉搜索树。
代码如下：
import random
class TreapNode:
"""Skapar en nod för det randomiserade binära sökträdet"""
def __init__(self, value = None, parent = None, left_child = None, right_child = None):
self.val = value
self.pri = random.randint(-1000, 1000)
self.par = parent
self.left = left_child
self.right = right_child
def addParent(self, p):
"""Tilldelar noden en förälder"""
self.par = p
def addLeft(self, lc):
"""Tilldelar noden ett barn till vänster"""
self.left = lc
def addRight(self, rc):
"""Tilldelar noden ett barn till höger"""
self.right = rc
def addValue(self, val):
"""Tilldelar noden ett värde, en s.k. adress"""
self.val = val
def getParent(self):
"""Returnerar nodens förälder"""
return self.par
def getLeft(self):
"""Returnerar nodens vänstra barn"""
return self.left
def getRight(self):
"""Returnerar nodens högra barn"""
return self.right
def getValue(self):
"""Returnerar nodens värde/adress"""
return self.val
def getPriority(self):
"""Returnerar nodens prioritet"""
return self.pri
class BalancedBinaryTree:
"""Skapar ett tomt binärt sökträd som är välbalanserat"""
def __init__(self):
self.root = None
self.size = 0
self.string = []
def rotate_left(self, u): # privat
"""Byter plats på noden u och dess högra barn genom rotation""" #denna algoritm bevarar
w = u.getRight() #"binära-sökträds" egenskapen
w.addParent(u.getParent) #hos varje nod
if w.getParent() != None:
p = w.getParent()
if p.getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addRight(w.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(w)
w.addLeft(u)
if w.getParent() == None:
self.root = w
def rotate_right(self, u): # privat
"""Byter plats på noden u och dess vänstra barn genom rotation""" #denna algoritm bevarar
w = u.getLeft() #"binära-sökträds" egenskapen
w.addParent(u.getParent()) #hos varje nod
if w.getParent() != None:
if w.getParent().getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addLeft(w.getRight())
if u.getLeft() != None:
u.getLeft().addParent(u)
u.addParent(w)
w.addRight(u)
if w.getParent() == None:
self.root = w
def add(self, val):
"""Låter användaren lägga till ett värde, men bara om det inte redan finns"""
u = TreapNode(value = val)
if self.add_node(val, u):
self.bubble_up(u)
self.size += 1
self.string.append(val)
return True
return False
def bubble_up(self, u): # prviat
"""Om prioriteten hos u är lägre än dess förälder, så byter u och föräldern plats"""
while u.getParent() != None and u.getParent().getPriority() > u.getPriority():
if u.getParent().getRight() == u:
self.rotate_left(u.getParent())
else:
self.rotate_right(u.getParent())
if u.getParent() == None:
self.root = u
def findString(self, val):
"""Låter användaren söka efter specifika värden. Returnerar värdet om det finns, annars None"""
w = self.root
while w != None:
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w.getValue()
return None
def add_node(self, val, node): # privat
"""Tilldelar ett löv ett barn med värdet val""" # här bryts inte "binär-
p = self.find_last(val) # sökträds" regeln
return self.add_child(p, node)
def find_last(self, val): #privat
"""Finner lämplig nod som kan tilldelas ett barn till höger/vänster med värdet val"""
w = self.root
prev = None
#if w != None:
# print(w.getValue())
#else:
# print(w)
while w != None:
prev = w
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w
return prev
def add_child(self, p, u): #privat
"""Tilldelar en nod p ett barn u till höger/vänster"""
if p == None:
self.root = u
else:
if u.getValue() < p.getValue():
p.addLeft(u)
u.addParent(p)
elif u.getValue() > p.getValue():
p.addRight(u)
u.addParent(p)
else:
print(u.getValue())
print(p.getValue())
return False
return True
def getSize(self):
return self.size
def orderedString(self):
if self.size == 0:
msg = "[]"
return msg
else:
orderedlist = sorted(self.string)
return orderedlist
def main():
# Testkod till TreapNode() klassen
nod = TreapNode()
nod.addParent(TreapNode(value = "abc", left_child = nod))
assert nod.getParent().getValue() == "abc"
assert nod.getParent().getLeft() == nod
assert -1000 <= nod.getPriority() <= 1000
nod.addRight(TreapNode(value=10, parent=nod))
nod.addValue("abcd")
assert nod.getRight().getValue() == 10
assert nod.getValue() == "abcd"
# Testkod till BalancedBinaryTree
tree = BalancedBinaryTree()
assert tree.orderedString() == "[]"
assert tree.getSize() == 0
assert tree.findString("abc") == None
tree.add("abc")
tree.add("aaa")
tree.add("bbb")
assert tree.orderedString() == ['aaa', 'abc', 'bbb']
assert tree.getSize() == 3
tree.add("hej")
tree.add("min")
tree.add("van")
tree.add("pa")
tree.add("andra")
tree.add("sidan")
tree.add("jorden")
tree.add("omg")
tree.add("lol")
tree.add("sos")
assert tree.orderedString() == ['aaa', 'abc', 'andra', 'bbb', 'hej', 'jorden', 'min', 'pa', 'sidan', 'van']
assert tree.getSize() == 10
tree.add("hej") # finns redan i trädet
assert tree.getSize() == 10 # alltså finns ingen dublett
assert tree.findString("hej") == "hej"
assert tree.findString("jorden") == "jorden"
assert tree.findString("sos") == "sos"
assert tree.findString("aldrig") == None
assert tree.findString("nagonsin") == None
# Tidskomplexitet för alla operationer:
#
# add() = O(nlog(n)) där n är antalet element
# findString() = O(log(n))
# getSize() = O(1)
# orderedString() = O(n), eftersom sorted() måste jämföra n element
if __name__ == "__main__":
main()
现在，当我执行这段代码时，我收到一条错误消息 AttributeError: 'function' object has no attribute 'getLeft'。好的，所以我检查传递给函数的对象，这似乎发生了：
作为节点对象的元素最终被传递给 rotate_left(self,u) 方法。这里的参数u就是nodeobject。我"reach"在这个nodeobject里面得到它的leftchild。然后我又在'reach'这个object内部返回Nodeobject，leftchildobjects就是所谓的parent。现在事情变得混乱了：Parentobject 在某种程度上是变态的。它应该与 Nodeobject 相同，但我看不出我做错了什么。如果我打印 nodeobject 及其 leftchild 和 leftchildParent，您会注意到其中的区别。
节点对象<__main__.TreapNode object at 0x7fcd32c90898>
Leftchildobject <__main__.TreapNode object at 0x7fcd32c908d0>
Leftchildobjects parent（这显然应该是上面的Nodeobject）<bound method TreapNode.getParent of <__main__.TreapNode object at 0x7fcd32c90898>>
最后一步发生了什么？
编辑
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.addParent(u.getRight())
p.addParent(u.getParent)
if p.getParent() != None:
if p.getParent().getLeft() == u:
p.getParent().addLeft(p)
else:
p.getParent().addRight(p)
u.addRight(p.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(p)
p.addLeft(u)
if p.getParent() == None:
self.root = p
这里是有些东西不起作用的方法。 if 语句 if p.getParent().getLeft() == u 引发了一个错误，即 AttributeError: 'function' object has no attribute 'getLeft'。我到底应该怎么做才能不引发此错误，对我来说看起来不错(?)
getParent是一个方法，你必须调用它来获取值。
w.addParent(u.getParent())
值得注意的是，getter/setter 模式在 Python 中并没有真正的意义，如果没有它，您的代码将大大简化。
编辑：
查看第 p.addParent(u.getParent) 行。那里发生的事情是您将 u.getParent 指定为 p 的父级。但是 u.getParent 是一种方法。因此，当您执行 p.getParent().getLeft() 时，这等同于 u.getParent.getLeft()，这不起作用，因为该方法没有 getLeft 方法。
关于 getter 和 setter：是什么让您认为您需要它们？您的方法可以很容易地
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.par = u.right
p.par = u.par # Is this what you intend to happen?
if p.par: # None is falsy
if p.par.left == u:
p.par.left = p
else:
p.par.right = p
u.right = p.left
if u.right:
u.right.par = u
u.par = p
p.left = u
if not p.par:
self.root = p
我也没有在您的对象中看到 __eq__ 方法。默认 __eq__ 方法仅 returns 如果两个对象是同一实例则为真。由于您在代码中使用 ==，这可能不是您想要的。