如何查找二进制树中是否存在值:True或False(Python3)

Question

我正在尝试编写一个代码，如果值存在于二进制树中，则输出返回True或False。

这是我的尝试：

定义一个名为Node:的类

class Node:
def __init__(self, data):

self.data = data
self.left = None
self.right = None

定义一个名为BinaryTree+LOOKUP函数的类：

class BinaryTree:
def __init__(self, rootdata):
self.root = Node(rootdata)
def LOOKUP(self, lookupval):
if lookupval < self.data:
if (self.left == None):
self.left.LOOKUP(lookupval)
return False
elif lookupval > self.data:
if (self.right == None):
self.right.LOOKUP(lookupval)
return False
else:
return True

其余，将值输入到二进制树：

Tree = BinaryTree(24)
Tree.root.left = Node(11)
Tree.root.left.left = Node(199)
Tree.root.left.right = Node(167)
Tree.root.right = Node(2)
Tree.root.right.right = Node(8)
print(Tree.LOOKUP(11))
print(Tree.LOOKUP(13))

然而，我一直得到错误'BinaryTree' object has no attribute 'data'。。

我知道函数LOOKUP的定义会有一些错误，但是我有没有机会保持这种格式并仍然返回输出：

True
False

谢谢你，

Answer 1

代码中的问题是：

• 您正在尝试引用self.right(应该是self.root.right，因为我们不在Node实例上(
• 嵌套的if检查错误。如果NOTNone或返回False，则应递归检查左/右树

这样做：

class Node:
def __init__(self, data):

self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, rootdata):
self.root = Node(rootdata)
def LOOKUP(self, lookupval):

if lookupval < self.root.data:
if self.root.left: 
return BinaryTree(self.root.left.data).LOOKUP(lookupval) # recursively check the left tree
else:
return False # can't go any further- so return false
elif lookupval > self.root.data:
if self.root.right:
return BinaryTree(self.root.right.data).LOOKUP(lookupval)
else:
return False
else:
return True
Tree = BinaryTree(24)
Tree.root.left = Node(11)
Tree.root.left.left = Node(199)
Tree.root.left.right = Node(167)
Tree.root.right = Node(2)
Tree.root.right.right = Node(8)
print(Tree.LOOKUP(11))
print(Tree.LOOKUP(13))

输出：

True
False