Check是python中的一个树，它是一个二进制搜索树

Question

我想写一个函数，显示给定的树是否为BinarySearch

这是我到目前为止写的：

class Node: 

     def _isBinary(self):
        
        L=[]

        if self.left is not None and self.right is not None:
            if self.left.data>self.data or self.right.data<self.data:
               L.append(1)
            else:
               L+=self.left._isBinary()
               L+=self.right._isBinary()
        else:

            if self.left is not None:
               if self.left.data>self.datat:
                  L.append(1)
               else:
                  self.left._isBinary()

            if self.right is not None:
               if self.right.data<self.data:
                  L.append(1)
               else:
                  self.right._isBinary()

       return L

class tree:
    
    def isBinary(self):
        if self.root is None:
            return
        else:
            return  not 1 in self.root._isBinary(self.root.data)

（很明显，我刚刚报告了代码中感兴趣的部分） 这段代码运行得很好，但给出了错误的答案，例如，当一个数字（大于根）位于树的左侧，但它是一个较低数字的子代时：

     99
    /  \
   8   888
    \
     100

它应该给我假，而不是返回真。我能做什么？（如果可能，在不完全更改原始代码的情况下？）

Answer 1

另一种方法是只按顺序遍历BST，然后检查它是否已排序。按顺序对BST的遍历进行排序

def inorder(node):
    if node is None:
        return
    yield from inorder(node.left)
    yield node.data
    yield from inorder(node.right)


inorder_traversal = list(inorder(root))
print(all(i<=j for i, j in zip(inorder_traversal, inorder_traversal[1:]))) # check if sorted

由于all的短路特性，您可以引入itertools.tee以获得更好的性能

inorder_traversal = inorder(root)
a, b = tee(inorder_traversal) # copy the `inorder_traversal` iterator
next(b) # discard first element
print(all(i<=j for i, j in zip(a,b))) # check if sorted

有关tee如何工作的更多信息，请参考此答案Iterate a list as pair (current, next) in Python

Answer 2

应采用以下方法：

class Node:
    def is_binary_search(self, lo=None, hi=None):
        if lo is not None and lo > self.data:
            return False
        if hi is not None and hi < self.data:
            return False
        if self.left and not self.left.is_binary_search(lo=lo, hi=self.data):
            return False
        if self.right and not self.right.is_binary_search(lo=self.data, hi=hi):
            return False
        return True

在递归调用中传递那些已知的子树边界（lo和hi）

Answer 3

您可以按顺序遍历树，并检查值是否为升序。使用迭代器可以避免创建任何列表

def iter(self):
    if self.left:  yield from self.left.iter()
    yield self
    if self.right: yield from self.right.iter()

from itertools import islice
def isBinary(self):
    return all(a<b for a,b in zip(self.iter(),islice(self.iter(),1,None)))