我想编写一个函数来显示给定的树是否是 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。我能做些什么？ （如果可能的话，不完全改变我原来的代码？）
另一种方法是对 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.teeallinorder_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
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）传递给递归调用。
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)))
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.right = right
self.left = left
这个简单的递归函数应该足够了。
将左子树和右子树的两个不同的比较器函数作为可调用参数传递给内部递归函数。
这不是最短的解决方案，但看起来不像黑魔法（希望如此）。
def is_bst(root):
def is_bst_recursive(node, in_order):
if node is None:
return True
if not in_order(node.value):
return False
if node.left and node.left.value >= node.value:
return False
if node.right and node.right.value <= node.value:
return False
return (is_bst_recursive(node.left, in_order)
and is_bst_recursive(node.right, in_order))
return (is_bst_recursive(root.left, lambda x: x < root.value)
and is_bst_recursive(root.right, lambda x: x > root.value))
is_binary_search
，它接受输入树
t和一个
compare函数，默认始终为
True-
def is_binary_search(t, compare = lambda _: True):
if not t:
return True
else:
return compare(t.data) \
and is_binary_search(t.left, lambda l: compare(l) and l < t.data) \
and is_binary_search(t.right, lambda r: compare(r) and r > t.data)
我们创建两棵树来测试我们的功能 -
t1，一个无效的二叉搜索树，在您的示例问题中提供
t2，一个有效的二叉搜索树
class node:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
t1 = \
node(99, node(8, None, node(100)), node(888))
# 99
# / \
# 8 888
# \
# 100
t2 = \
node(99, node(8, None, node(10)), node(888))
# 99
# / \
# 8 888
# \
# 10
print(is_binary_search(t1)) # False
print(is_binary_search(t2)) # True
我们还应该测试像空树、None
和只有单个节点的树这样的情况，每个树都是有效的二叉搜索树 -
print(is_binary_search(None)) # True
print(is_binary_search(node(123))) # True
def isbst(self,root):
if (root is None ):
return True
if(root is not None):
if (root.left is not None and root.left.data>=root.data):
return False
if (root.right is not None and root.right.data<root.data):
return False
return self.isbst(root.left) and self.isbst(root.right)