如何在树中搜索？

Question

我有这个跟随树实现：

class Node:
    def __init__(self, *, val):
        self.val = val

    def __repr__(self):
        return "{}(val={})".format(type(self).__name__, self.val)


class Tree:
    def __init__(self, *, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return "{}(val={}, left={}, right={})".format(type(self).__name__, self.val, self.left, self.right)

现在我尝试添加一个方法来检查元素是否存在：

def exists(self, val):
    if self.val == val:
        return True
    return self.left.exists(val) or self.right.exists(val)

然后，如果我尝试搜索 1，就没问题了。但是对于 2，它会出错。

Traceback (most recent call last):
  File "...", line 30, in <module>
    print(tree.exists(2))
  File "...", line 20, in exists
    return self.left.exists(val) or self.right.exists(val)
  File "...", line 20, in exists
    return self.left.exists(val) or self.right.exists(val)
AttributeError: 'Node' object has no attribute 'exists'

作为参考，这是我制作的树：

tree = Tree(val=1,
            left=Tree(val=Node(val=2), left=Node(val=3), right=Node(val=4)),
            right=Tree(val=Node(val=2), left=Node(val=3), right=Node(val=4)))

如何在树中递归搜索？

Answer 1

你递归的底部不仅是你找到了值（如果self.val == val），而且如果你到达树的叶子（如果self.isLeaf return假）

Answer 2

只需丢弃毫无用处的节点 class：

class Tree:
    def __init__(self, *, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def exists(self, val):
        if self.val == val:
            return True
        if self.left and self.left.exists(val):
            return True
        if self.right and self.right.exists(val):
            return True
        return False 

tree = Tree(val=1,
            left=Tree(val=2, left=Tree(val=3), right=Tree(val=4)),
            right=Tree(val=2, left=Tree(val=3), right=Tree(val=4)))

Answer 3

错误说“节点”没有“存在”的方法，这是正确的。您没有编写 Node 版本的“存在”。需要弄清楚每个节点有哪些数据和方法，整个树上应该有哪些数据和方法。

但是另外，如果不检查它们是否 None，你就不能向左或向右看。

self.left.exists()

应替换为

self.left and self.left.exists()

右边也一样

如何在树中搜索？

How to search in a tree?

python

tree

search

binary-tree

recursive-datastructures