如何調用算法中的二叉搜索樹

我正在嘗試創建一個簡單版本的拼寫檢查，它需要一個.txt文件並比較每個單詞是否在字典中找到。我已經建立了將.txt文件轉換爲列表和將字典轉換爲列表的功能，但我拼命地在我的拼寫檢查函數中調用了我的已排序二叉查找樹來查找字典。這是其次是我的拼寫檢查功能BinarySearchTree類如何調用算法中的二叉搜索樹

class BinarySearchTree: 

    def __init__(self): 
     self.root = None 

    def insert(self,val): 
     if self.root == None: 
      self.root = BinaryNode(val) 
     else: 
      self.recursive_insert(root,val) 

    def recursive_insert(self,parent,val): 
     if parent.data < val: 
      if parent.right != None: 
       self.recursive_insert(parent.right,val) 
      else: 
       parent.right = BinaryNode(val) 
     else: 
      if parent.left != None: 
       self.recursive_insert(parent.left,val) 
      else: 
       parent.left = BinaryNode(val) 

    def dictionary_insert(self,text): 
     for word in text: 
      self.insert(word) 

    def search(self,val): 
     if self.recursive_search(self.root,val) != None: 
      return True 
     else: 
      return False 

    def recursive_search(self,parent,val): 
     if parent.data == val: 
      return parent 
     elif parent.data > val: 
      return self.recursive_search(parent.left,val) 
     else: 
      return self.recursive_search(parent.right,val)

這裏是我的拼寫檢查功能：

def spell_checker(text): 

    N = len(text) 
    misspelled = 0 
    for i in range(N): 
     if BinarySearchTree().search(text[i]) == True: 
      misspelled = misspelled 
     else: 
      misspelled = misspelled + 1 
      print text[i] 
    if misspelled == 0: 
     print "There are no spelling errors!"

任何幫助將不勝感激。

來源

2013-12-11 user3068647

你的意思是「掙扎」？你有錯誤嗎？意外的輸出？ – jonrsharpe

當我通過BinarySearchTree.search引用調用recursive_search函數調用我在spell_checker – user3068647

中進行調用時，出現無類型'對象沒有任何屬性'數據的錯誤。然後：假設您調用recursive_search時使用了一個不在你的樹？當它落到一個沒有子節點的葉節點並且'parent.data'不等於'val'時會發生什麼？ –

當您第一次致電recursive_search時，您通過self.root作爲parent。但是，在__init__,self.root被設置爲None。因此嘗試訪問parent.data會給您一個錯誤，因爲None.data不存在。你需要做一個dictionary_insert，傳遞的有效單詞的列表，因爲您的安裝過程的一部分，使樹實際上它有句話：

dct = BinarySearchTree() 
dct.dictionary_insert(valid_word_list)

您還需要糾正的insert最後一行：

self.recursive_insert(self.root, val)

來源

2013-12-11 22:54:03 jonrsharpe

我試圖改變我的設置，他們的工作。我不確定我的插入功能。我將不得不深入探討 – user3068647

只是爲了一個答案填寫了這一點：

的recursive_search調用不正確處理失敗：

def recursive_search(self,parent,val): 
    if parent.data == val: 
     return parent 
    elif parent.data > val: 
     return self.recursive_search(parent.left,val) 
    else: 
     return self.recursive_search(parent.right,val)

如果在樹中根本找不到該單詞，最終將調用parent參數設置爲None，並且語句if parent.data == val:將拋出NoneType異常。

這裏的解決方案是返回None當parent == None：

def recursive_search(self,parent,val): 
    if parent == None: 
     return None 
    if parent.data == val: 
     return parent 
    elif parent.data > val: 
     return self.recursive_search(parent.left,val) 
    else: 
     return self.recursive_search(parent.right,val)

來源

2013-12-11 23:03:04

謝謝您的澄清！ – user3068647

如何調用算法中的二叉搜索樹

回答

相關問題