11 | 树的深度优先搜索（上）：如何才能高效率地查字典？

老师讲解得非常好，谈下个人对前缀树的了解，前缀树主要应用于以下场景： 1.预测文本输入功能：搜索引擎的输入框中输入搜索关键词的预测文本提示、IDE代码编辑器和浏览器网址中输入时的预测文本提示，借助老师讲的前两节动态规划实现预测文本的纠错功能； 2.使用前缀树结构对字符串或单词按字母顺序实现排序并进行输出的功能； 3.前缀树也可用于实现近似匹配，包括拼写检查和连字软件使用的算法； 前缀树的主要优劣对比： 1.使用前缀树可以高效地进行前缀搜索字符串和插入字符串，时间复杂度为O(length)； 2.使用前缀树可以按字母顺序轻松打印所有字符串，该功能是散列表不易实现的，但前缀树的搜索效率可能不如散列表快； 3.前缀树的缺点在于，需要大量的内存来存储字符串，对于每个节点需要太多的节点指针。倘若关注内存空间上的优化，可以考虑使用三元搜索树。三元搜索树是实现字典的首选结构，其搜索字符串的时间复杂度是O(height)；

下面是构建前缀树和查询的代码实现： package com.string.test; /** * Created by hanyonglu on 2019/1/7. */ public class TrieTest { private static final int CHARACTER_SIZE = 26; private TrieNode root; private static class TrieNode { private TrieNode[] children; private boolean isWordEnd; public TrieNode() { isWordEnd = false; children = new TrieNode[CHARACTER_SIZE]; for (int index = 0; index < CHARACTER_SIZE; index++) { children[index] = null; } } } public void insert(String key) { TrieNode newNode = root; int index; for (int i = 0; i < key.length(); i++) { index = key.charAt(i) - 'a'; if (newNode.children[index] == null) { newNode.children[index] = new TrieNode(); } newNode = newNode.children[index]; } newNode.isWordEnd = true; } public boolean search(String key) { TrieNode searchNode = root; int index; for (int i = 0; i < key.length(); i++) { index = key.charAt(i) - 'a'; if (searchNode.children[index] == null) { return false; } searchNode = searchNode.children[index]; } return (searchNode != null && searchNode.isWordEnd); } public static void main(String args[]) { String[] keys = {"my", "name", "is", "hanyonglu", "the", "son", "handongyang", "home", "near", "not", "their"}; TrieTest trieTest = new TrieTest(); trieTest.root = new TrieNode(); for (int index = 0; index < keys.length ; index++) { trieTest.insert(keys[index]); } System.out.println("home result : " + trieTest.search("home")); System.out.println("their result : " + trieTest.search("their")); System.out.println("t result : " + trieTest.search("t")); } }

关于思考题的一点想法：其实可以将单词以及字母抽象出来，利用组合模式，形成树形关系，实现递归调用。

对于二叉树而言，深度优先遍历是不是就是二叉树的先序遍历啊

正好最近刷到了leetcode上一道关于trie树的题 ## Algorithm ### 1. 题目 ``` 208. 实现 Trie (前缀树) ``` ### 2. 题目描述 ``` 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 示例: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true 说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。 ``` ### 3. 解答： ```golang type Trie struct { data byte child []*Trie isEnd bool } /** Initialize your data structure here. */ func Constructor() Trie { return Trie{ data: '/', child: make([]*Trie, 26, 26), isEnd: false, } } func newTrie(data byte) *Trie { return &Trie{ data: data, child: make([]*Trie, 26, 26), } } /** Inserts a word into the trie. */ func (t *Trie) Insert(word string) { p := t for _, c := range word { index := c - 'a' if p.child[index] == nil { p.child[index] = newTrie(byte(c)) } p = p.child[index] } p.isEnd = true } /** Returns if the word is in the trie. */ func (t *Trie) Search(word string) bool { p := t for _, c := range word { index := c - 'a' if p.child[index] == nil { return false } p = p.child[index] } if !p.isEnd { return false } else { return true } } /** Returns if there is any word in the trie that starts with the given prefix. */ func (t *Trie) StartsWith(prefix string) bool { p := t for _, c := range prefix { index := c - 'a' if p.child[index] == nil { return false } p = p.child[index] } return true } ``` ### 4. 说明 1. 定义Trie的结构中包含的child 2. child数组用26个英文字符表示，用字符减去`a`就得到数组中的索引

觉得二叉树跟正则表达式好像

这里的简单回路，其实就是指，除了第一个结点和最后一个结点相同外，其余结点不重复出现的回路？ 这句话怎么理解呢？ 其余结点不重复出现的回路？

把词都放在个数据库里，查询的时候用like，与把词放树里的效率哪个高？实现起来哪个简单？

讲得非常好

这次通俗易懂，感谢老师