如何查找二叉树中是否存在值：True或False（Python3）

Question

我试图编写一个代码，如果值存在于二叉树中，那么输出将返回True或False

以下是我的尝试：

定义名为Node的类：

class Node:

def __init__(self, data):
    
    self.data = data
    self.left = None
    self.right = None

定义名为BinaryTree+查找函数的类：

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'

我知道函数查找的定义会有一些错误， 但我是否有可能保留此格式并仍然返回输出：

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