程序员的数学基础课
黄申
LinkedIn 资深数据科学家
83374 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 58 讲
导读 (1讲)
基础思想篇 (18讲)
程序员的数学基础课
15
15
1.0x
00:00/00:00
登录|注册

12 | 树的深度优先搜索(下):如何才能高效率地查字典?

在一般的图中进行深度优先搜索的不同
使用栈实现深度优先搜索
遍历整个字典中所有的单词
递归中的处理
递归调用和深度优先搜索
递归编程
TreeNode类
二维数组
链表
数组
思考题
递归和栈实现深度优先搜索
数据结构表达树
树的深度优先搜索

该思维导图由 AI 生成,仅供参考

你好,我是黄申。今天咱们继续聊前缀树。
上节结尾我给你留了道思考题:如何实现前缀树的构建和查询?如果你动手尝试之后,你会发现,这个案例的实现没有我们前面讲的那些排列组合这么直观。
这是因为,从数学的思想,到最终的编程实现,其实需要一个比较长的过程。我们首先需要把问题转化成数学中的模型,然后使用数据结构和算法来刻画数学模型,最终才能落实到编码。
而在前缀树中,我们需要同时涉及树的结构、树的动态构建和深度优先搜索,这个实现过程相对比较复杂。所以,这节我就给你仔细讲解一下,这个实现过程中需要注意的点。只要掌握这些点,你就能轻而易举实现深度优先搜索。

如何使用数据结构表达树?

首先,我想问你一个问题,什么样的数据结构可以表示树?
我们知道,计算机中最基本的数据结构是数组和链表。
数组适合快速地随机访问。不过,数组并不适合稀疏的数列或者矩阵,而且数组中元素的插入和删除操作也比较低效。
相对于数组,链表的随机访问的效率更低,但是它的优势是,不必事先规定数据的数量,表示稀疏的数列或矩阵时,可以更有效地利用存储空间,同时也利于数据的动态插入和删除。
我们再来看树的特点。树的结点及其之间的边,和链表中的结点和链接在本质上是一样的,因此,我们可以模仿链表的结构,用编程语言中的指针或对象引用来构建树。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了前缀树的构建和查询方法,以及如何使用递归和栈实现深度优先搜索。通过介绍树的数据结构表示和动态构建方法,读者能够深入理解前缀树的实现原理和深度优先搜索的应用。文章详细阐述了前缀树的复杂性和需要注意的关键点,以及在查询过程中的处理方法。此外,通过使用栈来实现深度优先搜索,读者可以了解如何遍历整个字典中所有的单词。作者还提到了递归和深度优先搜索在归并排序和排列中的应用,强调了这些数学思想的相通性。总结来看,深度优先搜索的核心思想是按照当前的通路,不断地向前进,当遇到走不通的时候就回退到上一个结点,通过另一个新的边进行尝试。最后,作者提出了思考题,引发读者对一般图中进行深度优先搜索的不同之处的思考。整体而言,本文内容丰富,涵盖了树的深度优先搜索的多个方面,对读者进行了全面而深入的技术讲解。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《程序员的数学基础课》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(38)

  • 最新
  • 精选
  • Jsoulan
    感觉后面栈描述的过程像广度优先遍历呢

    作者回复: 栈是先进后出,还是深度优先。队列先进先出,适合广度优先

    2019-01-09
    23
  • pyhhou
    对于思考题: 1. 图中结点之间的关系是 “邻居”, 树中结点之间的关系 “父子”,如果是无向图,“邻居” 之间是互通的,但是 “父子” 默认是单向关系,一般遍历从 “父” 到 “子”,子结点中一般不保留父结点的信息 2. 图和树不一样的是,图会存在 “环” 的概念,就是回路,树中永远不可能有回路,否则就不是一棵树 可以说链表是特殊的树,树是特殊的图。 综上所述,对比树,在一般的图中做深度优先搜索的区别就是:我们需要记录我们之前访问过的结点,防止重复访问

    作者回复: 分析得很到位

    2019-03-12
    22
  • Wing·三金
    用 python 实现了 DFS 和字典树,比起 C++ 简直不要简单太多,感觉有点暴殄天物…… ### 在 python 中定义一个结点类 class Node: def __init__(self, alpha, pre, exp): self.alpha = alpha self.prefix = pre self.explanation = exp self.sons = dict() def find(self, alpha): if self.sons.get(alpha) == None: return False else: return True def create(self, alpha, son): self.sons[alpha] = son self.sons = {key: self.sons[key] for key in sorted(set(self.sons))} return True def get(self, alpha): return self.sons[alpha] class DictTree: def __init__(self, words, alpha=''): self.root = Node(alpha, '', '') self.build(words) def build(self, words): for word in words: self.add(word) def add(self, word): cur_node = self.root for i in word: i = i.lower() pre = cur_node.prefix + cur_node.alpha if not cur_node.find(i): cur_node.create(i, Node(i, pre, '')) cur_node = cur_node.get(i) cur_node.explanation = "This is a pyeudo explanation of '%s'" % word def DFS_search(self, word): word = word.lower() cur_node = self.root i = 0 while True: if i == len(word): if cur_node.explanation != '': return cur_node.explanation else: return "The word '%s' is not in this dictionary." % word if cur_node.find(word[i]): cur_node = cur_node.get(word[i]) i += 1 continue else: return "The word '%s' is not in this dictionary." % word DFS 的实现可以用 list 代替 stack,在“压入”时可以用 reversed 函数直接逆序。

    作者回复: 是的 Python简洁很多

    2019-03-19
    3
  • Ben
    第 3 步,将结点 123、879、945 和 131 压入栈中。 准确来说应该是 131, 945, 879, 123. 123是最后压栈的, 所以是最先出栈, 然后先处理123的子节点

    作者回复: 确实是,严格来说应该按照入栈的顺序来说

    2020-09-10
    2
  • Paul Shan
    这里深度优先遍历的顺序和前一篇文章中的不太一样,区别在于前一篇文章中的深度遍历,当发现一个新节点的时候入栈,然后马上处理这个新节点也就是栈顶,这篇文章中是把一个节点相连的所有节点入栈,然后再处理栈顶元素,请问老师,我的理解是否准确?

    作者回复: 是的,一个只要访问最深的某条路径,一个是需要遍历所有路径

    2019-08-23
    2
  • 张洋
    老师遍历出所有的单词 是不是用explanation判断更合适,因为一个通路是可以有多个单词的。 public static void dfsByStack(){ Stack<TreeNode> stack = new Stack<>(); stack.push(headNode); while(stack.size()>0){ TreeNode node = stack.pop(); if(!StringUtils.isEmpty(node.explanation)){ System.out.println(node.explanation); } Map<Character, TreeNode> sons = node.sons; sons.forEach((sonKey,sonValue)->{ stack.push(sonValue); }); } }

    作者回复: 这也是可以的,适用于字典的应用场景👍

    2019-10-22
    1
  • Joe
    老师讲解的树有多个分支,这里用C++简单演示了下二叉树的DFS。 /** * Objective:Given a b-tree, do the depth-first-search(DFS) or traversal. * Appraoch: stack, no recursion. * Example: * 1 * / \ * 2 3 * / \ / \ * 4 5 6 7 * Output: * preorder: 1 2 4 5 3 6 7 */ #include <iostream> #include <stack> using namespace std; // tree node class TreeNode { public: int data; TreeNode* left = NULL; TreeNode* right = NULL; public: TreeNode(int data) : data(data) { } }; // depth-first-search class DFS { public: void printDFS(TreeNode* root) { stack<TreeNode*> s; s.push(root); // begins! while (!s.empty()) { TreeNode* temp = s.top(); s.pop(); // push right first if (temp->right != NULL) { s.push(temp->right); } if (temp->left != NULL) { s.push(temp->left); } // print data cout << temp->data << " "; } } }; // test! int main(void) { // build tree. TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); DFS test; cout << "Depth-First-Search: " << endl; test.printDFS(root); } 输出: Depth-First-Search: 1 2 4 5 3 6 7

    作者回复: 很好的实现,代码简洁

    2019-01-17
    2
    1
  • Being
    广度优先一般用队列来做,FIFO,这样做到层级遍历;深度优先则用栈来做,FILO,这样做到按深度一条条的遍历下去。在实现上是这么区别的,我看上面有同学混淆了。

    作者回复: 总结的很好

    2019-01-09
    1
  • l c
    不是很理解为什么用显式栈实现dfs更省空间,我的理解中他们所用的空间是一样的。假使做全遍历,都是n(n为所有节点个数)。显式栈的优势不是只在于避免堆栈溢出吗?请老师解答一下。

    作者回复: 这个取决于每种语言和编程的具体实现是否有优化,如果没有优化,可能会导致每次嵌套调用的时候,都生成变量的副本

    2020-07-04
  • 咕咕咕
    那个用栈的应该属于bfs吧,虽说用的栈但还是一波一波往外扩的。

    作者回复: 栈一般用在dfs上,当然做适当修改也是可以做bfs,但是bfs队列就够了,所以不用了

    2020-05-08
收起评论
显示
设置
留言
38
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部