Python——迭代搜索树实现

Question

我正在尝试实现一个迭代函数，它在给定的搜索树中搜索一个整数，并报告该整数是否存在于搜索树中。到目前为止，如果值存在，它可以返回True，但在搜索树中不存在的值时会遇到"列表索引超出范围"错误。

return [l,v,r]
def left(l) :
return l[0]
def right(l) :
return l[2]
def value(l) :
return l[1]
def empty() :
return []

def iterative_check_for_elem(val,tree):
while not tree == False:
if val == value(tree):
return True
break
elif val < value(tree):
tree = left(tree)
elif val > value(tree):
tree = right(tree)
return False

test_tree = node(node(node(empty(),30,empty()),40,node(empty(),45,empty())),50,node(node(empty(),55,empty()),60,node(empty(),70,empty())))
print(iterative_check_for_elem(45,test_tree))

45在调用打印时工作，47遇到错误。老实说，我不知道出了什么问题。

Answer 1

您的树中有一堆空节点(由empty()创建(，您的搜索代码无法正确处理这些节点。虽然空列表是假的，但它不等于代码所期望的False。尝试将循环条件重写为：

while tree:
...

或者你可以更明确地做一个检查，比如：

while len(tree) > 0:
...