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

精选留言(19)

• 

  Handongyang

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

  作者回复: 总结的很好，还有实用的场景

  2019-01-07

   1

   21
• 

  Handongyang

  下面是构建前缀树和查询的代码实现：
  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"));
      }
  }

  作者回复: 实现很简洁👍

  2019-01-07

  

   13
• 

  产品助理

  从起始点到终止点所经过的边之数量，就是通路的长度。这里我画了...
  
  极客时间版权所有: https://time.geekbang.org/column/article/76481
  
  这里的通路的长度应该是3啊。
  
  边有：v1——v2，v2——v3，v3——v4 三条，所以边的长度是3对吗？

  作者回复: 对 应该是3，我稍后该一下

  2019-01-07

   1

   5
• 

  是我

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

  作者回复: 具体是哪种正则表达式？

  2019-05-16

   1

   1
• 

  qinggeouye

  查找到一个 python 版本，分别用迭代循环和递归的方法，实现在树中添加和查找单词。动手实现了一遍：～
  https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/11_deepFirstSearch/lesson11_1.py
  
  

  2019-02-20

  

   1
• 

  asc

  老师讲的很好，非常容易理解。😁这次就不做作业了

  2019-01-09

  

   1
• 

  Being

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

  作者回复: 如果使用前缀树，对给定的一些单词进行处理，就无需排列组合了

  2019-01-07

  

   1
• 

  建强

  用Python写了一个简单的程序：
  # 前缀树构造与查询
  
  # 前缀树节点
  class PrefixNode:
      def __init__(self, letter):
          self.letter = letter # 每个节点中存储一个单词的字母
          self.childnode = {} # 子节点用字典存储
          self.isend = False # isend表示单词是否结束
  
      def addchild(self, child):
          self.childnode[child.letter] = child
  
      # 寻找字母为letter的子节点
      def findchild(self, letter):
          return self.childnode.get(letter)
  
  # 前缀树
  class PrefixTree:
      def __init__(self):
          self.root = PrefixNode('#') # 用#号代表根节点
  
      # 向字典树中加入一个单词
      def addWord(self, word):
          p = self.root
          for w in word:
              childnode = p.findchild(w)
              if childnode is None:
                  # 前缀树中没有找到对应的字母，则重新构造一个新的子节点
                  childnode = PrefixNode(w)
                  p.addchild(childnode)
  
              p = childnode
              
          p.isend = True
  
      # 在字典树中查找一个单词
      def searchWord(self, word):
          p = self.root
          for w in word:
              childnode = p.findchild(w)
  
              if childnode is None:
                  # 前缀树中没有找到对应的字母，则直接返回False
                  return False
  
              p = childnode
              
          return p.isend
  
  # 主程序
  def main():
      # 构造字典树
      dict_tree = PrefixTree()
      
      # 向字典树中加入一些单词
      for word in ['beautiful','student','computer','desk','table','design','book','bookshelf']:
          dict_tree.addWord(word)
  
      print('prefix tree is maded')
  
      # 在字典树中查找单词
      for word in ['beau', 'book','student', 'conputer', 'bookshelf', 'desks']:
          if dict_tree.searchWord(word):
              print('"{}" was founded.'.format(word))
          else:
              print('"{}" was not founded.'.format(word))
          
  if __name__ == '__main__':
      main()

  2019-12-07

  

  
• 

  aoe

  这次通俗易懂，感谢老师

  作者回复: 很高兴对你有价值

  2019-12-02

  

  
• 

  Eleven

  老师，这篇概念有点多啊，文章中说的有向边该怎么理解呢？

  作者回复: 有向边是指从某个节点到另一个节点存在方向，顺向可以走通，逆向就不行

  2019-11-25

  

  
• 

  花指令

  发现大家用循环遍历确定节点，既然是字母，大小写最多就52个，那应该用ascii做二分搜索更快，分布均匀的话还可以直接用数组下标

  作者回复: 如果只限定在英文，这是个好方法👍

  2019-11-04

  

  
• 

  AlphaZero

  Golang 版：
  
  package main
  
  import "fmt"
  
  func main() {
  dict := NewDictionary()
  dict.Insert("hello", "你好")
  dict.Insert("世界", "word")
  
  fmt.Println(*dict.Explain("hello"))
  fmt.Println(*dict.Explain("世界"))
  }
  
  type trieNode struct {
  char rune
  children []*trieNode
  explanation *string
  }
  
  type Dictionary struct {
  root *trieNode
  }
  
  // Insert adds the word to the dictionary
  func (dict *Dictionary) Insert(word string, explanation string) {
  current := dict.root
  for _, ch := range []rune(word) {
  found := false
  
  if len(current.children) > 0 {
  for _, node := range current.children {
  if node.char == ch {
  current = node
  found = true
  break
  }
  }
  }
  
  if !found {
  child := &trieNode{char: ch}
  current.children = append(current.children, child)
  current = child
  }
  }
  
  if current.explanation == nil || *current.explanation != explanation {
  current.explanation = &explanation
  }
  }
  
  // Explain returns the explanation of the given word
  func (dict *Dictionary) Explain(word string) *string {
  current := dict.root
  for _, ch := range []rune(word) {
  found := false
  for _, node := range current.children {
  if node.char == ch {
  current = node
  found = true
  break
  }
  }
  
  if !found {
  return nil
  }
  }
  
  return current.explanation
  }
  
  // NewDictionary create a empty Trie
  func NewDictionary() *Dictionary {
  return &Dictionary{
  root: &trieNode{
  char: ' ',
  },
  }
  }

  2019-09-30

  

  
• 

  Paul Shan

  树是一种递归结构，由根节点和若干子树构成。在建树和查找上也会充分利用这种递归结构。

  2019-08-22

  

  
• 

  Better me

  想问下老师最后小结中对应的左子树为0右子树为1对应的二进制数有什么实际应用场景吗

  作者回复: 其实二进制表示的本身就是最好的应用场景。当然，二分法也是一种对应的实现

  2019-07-28

  

  
• 

  梦倚栏杆

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

  作者回复: 确切的说，先序、中序和后序是深度优先遍历的三种方式

  2019-03-26

  

  
• 

  pyhhou

  简单实现了下，跑了几个例子是可以work的，这里build的时候用Map是考虑到字典里面的单词和解释以key-value的形式出现，search函数输入是单词输出是解释，没有该单词的话返回null
  
  public class Trie {
       private class TrieNode {
            private TrieNode[] children = new TrieNode[26];
            private String word = null;
            private String explanation = null;
       }
  
       private TrieNode root = new TrieNode();
  
            public void buildTrie(Map<String, String> dictionary) {
                 if (dictionary == null || dictionary.size() == 0) {
                      return;
                 }
  
                 for (String word : dictionary.keySet()) {
                      char[] wordArr = word.toCharArray();
                      TrieNode tmp = root;
  
                       for (char c : wordArr) {
                            if (tmp.children[c - 'a'] == null) {
                                 tmp.children[c - 'a'] = new TrieNode();
                            }
                            tmp = tmp.children[c - 'a'];
                       }
  
                       tmp.word = word;
                       tmp.explanation = dictionary.get(word);
                  }
             }
  
            public String searchTrie(String targetWord) {
                 if (targetWord == null || targetWord.isEmpty()) {
                      return null;
                 }
  
                 char[] targetWordArr = targetWord.toCharArray();
                 TrieNode tmp = root;
  
                 for (char c : targetWordArr) {
                      if (tmp.children[c - 'a'] == null) {
                           return null;
                      }
  
                      tmp = tmp.children[c - 'a'];
                  }
  
             return tmp.explanation;
        }

  作者回复: 逻辑上没问题，使用26个英文字母对于字典而言足够了👍

  2019-01-18

  

  
• 

  李尧

  老师好，根节点的高度可以随意设置吗，假如设置为1，子节点的高度是不是都需要加1

  作者回复: 是的 通常根结点高度只会设置为0或1

  2019-01-07

  

  
• 

  alic

  哪位大佬实现了放上去看一下

  2019-01-07

  

  
• 

  WL

  不错不错, 又把大学忘掉的知识复习了一遍

  2019-01-07

  

  