統(tǒng)計(jì)
          
	
		

          留言簿(1)
          


        
		
		
          DB
          
		
				
			
	
		
          Others
          
		
				
			
	
		
          QA
          
		
				
			
	
		
          Tech Website
          
		
				
			
	

        

          閱讀排行榜
          


		

          評(píng)論排行榜
          


	

          

          
	
					
	
          
		
          
			Trie Tree
		
          
		
          #Trie Tree的基本特點(diǎn)
          1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符 
          2）從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串
          3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同

          

          原理圖：


          參考：
          數(shù)據(jù)結(jié)構(gòu)之Trie樹
          Trie Tree on Answers.com

          #Trie Tree簡(jiǎn)單的Python實(shí)現(xiàn)
          最近在學(xué)習(xí)Python，下面的代碼就用來學(xué)習(xí)下語法了 ：）
          

          #coding:utf-8
          '''
          Created on 2011-6-14

          @author: Dokie
          '''
          ALPHABET_SIZE           = 26

          class Node:
              
                        def __init__(self, is_end = False):
                  self.is_end           = is_end
                  self.prefix_count           = 0
                  self.children           = [None for child in range(ALPHABET_SIZE)]

          class Trie:
                        def __init__(self):
                  self.head           = Node()
                  
                        def insert(self, word):
                  current           = self.head
                  count           = 0
                            for letter in word:
                      int_value           = ord(letter) - ord('a')
                                try:
                                    assert ( 0 <= int_value <= 26)
                                except Exception:
                                    raise Exception("invalid Word")
                      
                                if current.children[int_value] is None:
                          current.children[int_value]           = Node()
                          current           = current.children[int_value]
                          count           += 1
                          current.prefix_count           = count
                  current.is_end           = True
                  
                        def search(self, word):
                  
                  current           = self.head
                            for letter in word:
                      int_value           = ord(letter) - ord('a')
                                try:
                                    assert (0 <= int_value <= 26)
                                except Exception:
                                    return False
                                if current.children[int_value] is None:
                                    return False
                                else:
                          current           = current.children[int_value]
                          
                                return current.is_end


                  
                  
                   
                        def count_words_with_prefix(self, word):
                  current           = self.head
                            for letter in word:
                      int_value           = ord(letter) - ord('a')
                                try:
                                    assert (0 <= int_value <= 26)
                                except Exception:
                                    return None
                                if current.children[int_value] is None:
                                    return None
                                else:
                          current           =  current.children[int_value]
                            return current.prefix_count
                          

                  
          if __name__ == '__main__':
                        import doctest
              doctest.testmod()
              t           = Trie()
              t.insert(          "apple")
              t.insert(          "good")
                        print t.search("apple")
                        print t.search("fff")
                        print t.count_words_with_prefix("apple")
          

          附：TrieMap Javap實(shí)現(xiàn)

          
		
          
			posted on 2011-06-14 16:57 XXXXXX 閱讀(1085) 評(píng)論(0)  編輯  收藏  所屬分類: Algorithm 
		
          
	
          
	
	


	


          
	    
    




          








          

				

          



    







          
        
	




主站蜘蛛池模板：
浦东新区|
阿合奇县|
金华市|
奎屯市|
原阳县|
绥化市|
陵川县|
安康市|
香格里拉县|
桐梓县|
泰顺县|
陆川县|
华蓥市|
通州市|
平安县|
同德县|
东乌|
五家渠市|
五华县|
湘乡市|
托里县|
洱源县|
安达市|
津南区|
竹溪县|
靖江市|
昆明市|
石阡县|
芮城县|
邯郸县|
洪江市|
新干县|
孟连|
南乐县|
绍兴市|
库车县|
将乐县|
济阳县|
夹江县|
冷水江市|
行唐县|