统计

留言簿(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 阅读(1075) 评论(0)  编辑  收藏 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: