如何从 python 中的二叉搜索树中查找值？

Question

我想创建一个交互式二叉搜索树 (BST)。所以我使用以下代码创建了 BST

class BTreeNode(object):
  def __init__(self, data):
    self.data = data
    self.rChild = None
    self.lChild = None

  def __str__(self):
    return (self.lChild.__str__() + '<-' if self.lChild != None 
    else '') + self.data.__str__() + (
    '->' + self.rChild.__str__() if self.rChild != None else '')

  # Insert method to create nodes
  def insert(self, btreeNode):
    if self.data > btreeNode.data:  # insert left
        if self.lChild == None:
            self.lChild = btreeNode
        else:
            self.lChild.insert(btreeNode)
    else:  # insert right
        if self.rChild == None:
            self.rChild = btreeNode
        else:
            self.rChild.insert(btreeNode)
  # Insert method to create nodes

  # findval method to compare the value with nodes
  def findval(self, lkpval):
    if lkpval < self.data:
        if self.lChild.data is None:
            return str(lkpval)+" Not Found"
        return self.lChild.findval(lkpval)
    elif lkpval > self.data:
        if self.rChild.data is None:
            return str(lkpval)+" Not Found"
        return self.rChild.findval(lkpval)
    else:
        print(str(self.data) + ' is found')
  # findval method to compare the value with nodes

def display():
 btreeRoot = BTreeNode(5)
 print('inserted %s:' % 5, btreeRoot)

 btreeRoot.insert(BTreeNode(7))
 print('inserted %s:' % 7, btreeRoot)

 btreeRoot.insert(BTreeNode(3))
 print('inserted %s:' % 3, btreeRoot)

 btreeRoot.insert(BTreeNode(1))
 print('inserted %s:' % 1, btreeRoot)

 # print(btreeRoot.findval(3))

print(display())

如果我执行上面的代码，我将得到以下交互式输出

inserted 5: 5

inserted 7: 5->7

inserted 3: 3<-5->7

inserted 1: 1<-3<-5->7

这是我的预期输出，我明白了。另外，我想从 BST 中找到一个值。所以我在显示函数中使用了如下代码as

# print(btreeRoot.findval(3))

如果我取消注释代码，我会得到错误。那么，如何修改代码以显示 BST 中是否存在 3？谢谢..

Answer 1

执行检查 if self.lChild.data is None 和 if self.rChild.data is None 时出现问题。这些行应分别替换为 if self.lChild is None 和 if self.rChild is None，因为您的 class 暗示这些属性是 None 的，而不是它们的 data 属性。

也可以考虑使用 is None 而不是 == None。在这种情况下这不是什么大问题，但在其他情况下可能会造成麻烦。在这里查看详细信息：Python None comparison: should I use "is" or ==?

如何从 python 中的二叉搜索树中查找值？

How to find a value from a Binary Search Tree in python?

binary-tree

binary-search-tree

python-3.x