Python - Итеративная реализация дерева поиска - PullRequest
Новая
       12

Python - Итеративная реализация дерева поиска

0 голосов
/ 18 апреля 2020

Я пытаюсь реализовать итеративную функцию, которая ищет заданное дерево поиска для целого числа и сообщает, существует ли это целое число в дереве поиска. До сих пор он работает для возврата 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 сталкивается с ошибкой. Я не могу понять, что происходит честно.

1 Ответ

0 голосов
/ 18 апреля 2020

В вашем дереве есть куча пустых узлов (созданных empty()), и ваш поисковый код не работает с ними должным образом. Хотя пустой список ложный, он не равен False, чего, по-видимому, ожидает ваш код. Попробуйте переписать условие l oop следующим образом: 

while tree:
    ...

Или вы можете быть более явным и выполнить проверку как: 

while len(tree) > 0:
    ...
...