字典树Trie，又称为前缀树Prefix tree，是一个26叉树，用于在一个集合中检索一个字符串，或者字符串前缀。

image.png

Trie树的两个部分：

  • Node类
    • 判断当前节点是否是某个字符串的结尾
    • 根据字符，查找后继节点
  • 类方法
    • 插入字符串
    • 字符串查询

代码

  1. class Node:
  3.     def __init__(self, is_leaf=False):
  4.         self.chicd = {}
  5.         self._is_leaf = is_leaf
  7.     @property
  8.     def is_leaf(self):
  9.         return self._is_leaf
  11.     @is_leaf.setter
  12.     def is_leaf(self, is_leaf):
  13.         self._is_leaf = is_leaf
  15.     def put(self, key, value):
  16.         self.chicd[key] = value
  18.     def get_next_node(self, _str):
  19.         if len(_str) != 1:
  20.             return None
  21.         return self.chicd.get(_str, None)
  23.     def get_node(self, key):
  24.         return self.chicd.get(key, None)
  26. class Trie:
  28.     def __init__(self):
  29.         self.root = Node()
  31.     def insert(self, _str):
  32.         cur = self.root
  33.         for c in _str:
  34.             if cur.get_next_node(c) is None:
  35.                 cur.put(c, Node())
  36.                 cur = cur.get_node(c)
  37.             else:
  38.                 cur = cur.get_next_node(c)
  39.         cur.is_leaf = True
  41.     def query(self, _str):
  42.         cur = self.root
  43.         for c in _str:
  44.             if cur.get_next_node(c) is None:
  45.                 return False
  46.             cur = cur.get_next_node(c)
  47.         return cur.is_leaf
  49. if __name__ == "__main__":
  50.     trie = Trie()
  51.     trie.insert('abcda')
  52.     trie.insert('absde')
  53.     trie.insert('eecdab')
  54.     trie.insert('wemo')
  55.     trie.insert('azhu')
  57.     print(trie.query('wemo'))
  58.     print(trie.query('ab'))
  59.     print(trie.query('jun'))

image.png