检查是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

它应该给我 False，而不是它返回 True。我能做什么？（如果可能，不完全改变我的原始代码？）

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

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

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。