时间戳

首页 > 解决方案 > Python - 迭代搜索树实现

python - Python - 迭代搜索树实现

问题描述

我正在尝试实现一个迭代函数，它在给定的搜索树中搜索一个整数，并报告该整数是否存在于搜索树中。到目前为止，如果值存在则返回 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 遇到错误。老实说，我无法弄清楚出了什么问题。

标签： pythoniterationlimit

解决方案

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

while tree:
    ...

或者您可以更明确地进行如下检查：

while len(tree) > 0:
    ...

推荐阅读