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

精选留言(12)

• 
  Handongya...

  2019-01-07

   12

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

  展开

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

• 
  Handongya...

  2019-01-07

   6

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

   2

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

  展开

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

• 
  qinggeouy...

  2019-02-20

   1

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

  展开
• 
  asc

  2019-01-09

   1

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

  展开
• 
  Being

  2019-01-07

   1

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

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

• 
  是我

  2019-05-16

  

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

  展开

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

• 梦倚栏杆

  2019-03-26

  

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

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

• pyhhou

  2019-01-18

  

  简单实现了下，跑了几个例子是可以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-07

  

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

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

• 
  alic

  2019-01-07

  

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

  展开
• 
  WL

  2019-01-07

  

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

  展开