二分查找树Python。迭代搜索

Question

我想知道是否有人可以帮助我看看我用二叉搜索树的搜索函数做错了什么。由于数据量太大，必须使用迭代版本。当我打印出调试值时，我总是陷入无限的 while 循环。谢谢！

我也收到此错误：

while (word_search.value != user_input) and (word_search.value != None):
    AttributeError: 'NoneType' object has no attribute 'value'

    def iterative_word_search(current, user_input):
            word_search = current.root
            print("User input value", user_input)
            print("Word Search Value", word_search.value)

            while (word_search.value != None) and (word_search.value != user_input):
                print("While Loop value: ", word_search.value)      
                if(user_input < word_search.value):
                  word_search = word_search.left
    #              print("If statement value: " ,word_search.value)
                elif(word_search.right != None):
                  word_search = word_search.right
                  print("Else statement value: ", word_search.value)
                elif(word_search.value == None):
                    print("Word does not exist")
                    return word_search
            return word_search

Answer 1

在调用

left

之前，您需要断言

right

和

None

不是

.value

：

表达式的

Python lazy evaluation 允许您在一行内完成此操作。

if word_search is None or word_search.value is None

会评估

word_search

，如果是

None

，则不会评估

word_search.value

。

def iterative_word_search(current, user_input):

    word_search = current.root

    while True:
        if word_search is None or word_search.value is None:
            print("not found")
            break
        if word_search.value == user_input:
            print("found")
            break
        if(user_input < word_search.value):
            word_search = word_search.left
        elif(word_search.right != None):
            word_search = word_search.right

    return word_search 

Answer 2

感谢大家的帮助！ 解决了问题。它处理用户输入和我读入的文件。 我读入的文件附加了“\N”。这就是为什么我不断收到多个错误并且它没有搜索这个词。

Answer 3

def迭代（自身，根，值）： while（根不是 None ）：

    if(root.data==value):
       return True

    if ( value>root.data):
     root=root.right
    if (value<root.data):
     root=root.left
        
  return False