输入输出为>>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t1) True >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)]) >>> is_bst(t2) False >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t3) False >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])]) >>> is_bst(t4) True >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])]) >>> is_bst(t5) True >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])]) >>> is_bst(t6) True >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)]) >>> is_bst(t7) False请写代码，其中class Tree: def init(self, label, branches=[]): for b in branches: assert isinstance(b, Tree) self.label = label self.branches = list(branches) def is_leaf(self): return not self.branches def map(self, fn): self.label = fn(self.label) for b in self.branches: b.map(fn) def contains(self, e): if self.label == e: return True for b in self.branches: if e in b: return True return False def repr(self): if self.branches: branch_str = ', ' + repr(self.branches) else: branch_str = '' return 'Tree({0}{1})'.format(self.label, branch_str) def str(self): def print_tree(t, indent=0): tree_str = ' ' * indent + str(t.label) + "\n" for b in t.branches: tree_str += print_tree(b, indent + 1) return tree_str return print_tree(self).rstrip()

下面是判断一棵二叉树是否为二叉搜索树的代码实现：

class Tree:
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = list(branches)

def is_leaf(self):
return not self.branches

def map(self, fn):
self.label = fn(self.label)
for b in self.branches:
b.map(fn)

def contains(self, e):
if self.label == e:
return True
for b in self.branches:
if e in b:
return True
return False

def __repr__(self):
if self.branches:
branch_str = ', ' + repr(self.branches)
else:
branch_str = ''
return 'Tree({0}{1})'.format(self.label, branch_str)

def __str__(self):
def print_tree(t, indent=0):
tree_str = ' ' * indent + str(t.label) + "\n"
for b in t.branches:
tree_str += print_tree(b, indent + 1)
return tree_str
return print_tree(self).rstrip()

def is_bst_helper(t, min_val, max_val):
if t is None:
return True
if t.label < min_val or t.label > max_val:
return False
return is_bst_helper(t.branches[0], min_val, t.label-1) and is_bst_helper(t.branches[-1], t.label+1, max_val)

def is_bst(t):
return is_bst_helper(t, float('-inf'), float('inf'))

# 测试样例
t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
print(is_bst(t1)) # True

t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
print(is_bst(t2)) # False

t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
print(is_bst(t3)) # False

t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
print(is_bst(t4)) # True

t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
print(is_bst(t5)) # True

t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
print(is_bst(t6)) # True

t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
print(is_bst(t7)) # False