__contains__方法在二进制搜索树Python中是如何工作的？

Question

我有两个类，Node（）和binarySearchTree（）。 Node（）具有以下属性：

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

binarySearchTree（）具有插入、搜索和打印二进制搜索树（BST）的方法。我还必须为我的BST包含一个__contains__方法，它使我能够编写如下内容：

tree= Bintree()
tree.store("table")
 
if "table" in tree:  <--
    do something     <--

它抱怨最后两个“__contains__”没有定义。但我希望它能递归地工作。但它不起作用

    def __contains__(self, key):
        if self.root == None:
            return False
        elif key== self.root.key:
            return True
        elif key < self.root.key:
            return __contains__(self.root.key.left,key)
        elif key > self.root.key:
            return __contains__(self.root.key.right,key)

Answer 1

如果有单独的树和节点类型，则需要两个函数，一个通过节点递归，另一个只是为了让事情继续进行

大概是这样的：

def __contains__(self, key):
    returns self.node_contains(self.root, key)

def node_contains(self, node, key):
    if node == None:
        return False
    elif key == node.key:
        return True
    elif key < node.key:
        return self.node_contains(node.left, key)
    elif key > node.key:
        return self.node_contains(node.right, key)

或者，您可以将工作划分为两个类，如下所示

在树类中：

def __contains__(self, key):
    return self.root and key in self.root

在节点类中：

def __contains__(self, key):
    return self.key == key 
        or (key < self.key and self.left and key in self.left) 
        or (self.right and key in self.right)

Answer 2

__contains__不是全局变量；它是一个类属性，因此必须通过BinTree或其实例之一进行访问。至少，你需要写作

def __contains__(self, key):
    if self.root == None:
        return False
    elif key == self.root.key:
        return True
    elif key < self.root.key:
        return BinTree.__contains__(self.root.left, key)
    elif key > self.root.key:
        return BinTree.__contains__(self.root.right, key)

（请注意，第一个参数中不需要key属性；具有left和right属性的是self.root本身，而不是它的键

但是，这只是调用实例属性的一种非标准方法，它会阻止继承正确工作。如果您更改类的名称而不更新方法的定义以使用新名称，它也会失败。下一个最好的方法是正常调用该方法

def __contains__(self, key):
    if self.root == None:
        return False
    elif key == self.root.key:
        return True
    elif key < self.root.key:
        return self.root.left.__contains__(key)
    elif key > self.root.key:
        return self.root.right.__contains__(key)

但最重要的是不要直接调用__contains__，而是使用来使用in，这将为您调用__contains__

def __contains__(self, key):
    if self.root == None:
        return False
    elif key == self.root.key:
        return True
    elif key < self.root.key:
        return key in self.root.left
    else:  # key > self.root.key is the only option left
        return key in self.root.right

警告：以上所有假设self.root.left和self.root.right存在且不是None，这一假设可能不准确，但如果没有显示BinTree如何构造的代码，则无法确认

Answer 3

琐碎的修理

     1      def __contains__(self, key):
     2          if self.root == None:
     3              return False
     4          elif key== self.root.key:
     5              return True
     6          elif key < self.root.key:
     7              return self.__contains__(self.root.key.left,key)
     8          elif key > self.root.key:
     9              return self.__contains__(self.root.key.right,key)

只要打电话self.__contains__