原文地址:
https://my.oschina.net/goal/blog/200596

leetcode 也有很详细的介绍以及字典树的应用场景
https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/

字典树,前缀树

class Node(object):

    def __init__(self, c=None, word=None):

        self.c = c # 节点存储的单个字符
        self.word = word
        self.child = [] # 这个节点的子节点


class Trie(object):
    def __init__(self):
        self.root = Node()

    def find(self, node, c):
        """查找字符插入的位置"""
        child = node.child
        length = len(child) # 查看node节点有多少个子节点
        if length == 0:
            return -1
        for i in range(length):
            if child[i].c == c: # 和当前节点存储的字符比较,是否相同
                return i
        return -1

    def add(self, word):
        """添加字符串"""
        node = self.root
        for c in word:
            pos = self.find(node, c)
            if pos < 0:
                # 表示当前节点的所有子节点都没有相同的
                # 没有就创造
                node.child.insert(0, Node(c))
                pos = 0
            node = node.child[pos] # 移动到下一个子节点上
        node.word = word

    def pre_order(self, node):
        """先序输出"""
        results = []
        if node.word:
            results.append(node.word)
        for child in node.child:
            # 遍历所有子节点
            results.extend(self.pre_order(child))
        return results

    def setword(self, words):
        for word in words:
            self.add(word)


if __name__ == '__main__':
    obj = Trie()
    words = ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
    obj.setword(words)
    print(obj.pre_order(obj.root))

使用Python字典实现

class Trie(object):

    def __init__(self):
        self.root = {}
        self.end = -1

    def insert(self, word):
        cur_node = self.root
        for c in word:
            if c not in cur_node:
                cur_node[c] = {}
            cur_node = cur_node[c]
        cur_node[self.end] = True

    def search(self, word):
        cur_node = self.root
        for c in word:
            if c not in cur_node:
                return False
            cur_node = cur_node[c]

        # 整个遍历完成,则代表存在于这个前缀树中
        if self.end not in cur_node:
            return False
        return True

    def startswith(self, prefix):
        """返回字典树中,是否有prefix开头的字符串"""
        cur_node = self.root
        for c in prefix:
            if c not in cur_node:
                return False
            cur_node = cur_node[c]
        # 遍历结束,则前面字符是一致的
        return True
Last modification:March 23rd, 2020 at 05:16 pm