统计

留言簿(1)

DB

Others

QA

Tech Website

阅读排行榜

评论排行榜

Trie Tree

#Trie Tree的基本特点
1)根节点不包含字符,除根节点外每个节点只包含一个字符
2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串
3)每个节点的所有子节点包含的字符串不相同

原理图:


参考:
数据结构之Trie树
Trie Tree on Answers.com

#Trie Tree简单的Python实现
最近在学习Python,下面的代码就用来学习下语法了 :)

#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实现


posted on 2011-06-14 16:57 XXXXXX 阅读(1074) 评论(0)  编辑  收藏 所属分类: Algorithm


只有注册用户登录后才能发表评论。


网站导航: