Python实现简单字典树的方法

本文实例讲述了Python实现简单字典树的方法。分享给大家供大家参考，具体如下：

    #coding=utf8
    """代码实现了最简单的字典树，只支持由小写字母组成的字符串。
    在此代码基础上扩展一下，就可以实现比较复杂的字典树，比如带统计数的，或支持更多字符的字典树，
    或者是支持删除等操作。
    """
    class TrieNode(object):
      def __init__(self):
        # 是否构成一个完成的单词
        self.is_word = False
        self.children = [None] * 26
    class Trie(object):
      def __init__(self):
        self.root = TrieNode()
      def add(self, s):
        """Add a string to this trie."""
        p = self.root
        n = len(s)
        for i in range(n):
          if p.children[ord(s[i]) - ord('a')] is None:
            new_node = TrieNode()
            if i == n - 1:
              new_node.is_word = True
            p.children[ord(s[i]) - ord('a')] = new_node
            p = new_node
          else:
            p = p.children[ord(s[i]) - ord('a')]
            if i == n - 1:
              p.is_word = True
              return
      def search(self, s):
        """Judge whether s is in this trie."""
        p = self.root
        for c in s:
          p = p.children[ord(c) - ord('a')]
          if p is None:
            return False
        if p.is_word:
          return True
        else:
          return False
    if __name__ == '__main__':
      trie = Trie()
      trie.add('str')
      trie.add('acb')
      trie.add('acblde')
      print trie.search('acb')
      print trie.search('ac')
      trie.add('ac')
      print trie.search('ac')

更多关于Python相关内容可查看本站专题：《Python字典操作技巧汇总》、《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。