知识卡片
遍历次序决定展开路径
深度优先先沿一条分支继续向下,直到不能再下去才回退并处理其他分支;广度优先先处理同层节点,再向下一层展开。四叉细分的递归调用顺序给出了深度优先的一种执行路径。
树是无环结构的一种,但一般有向无环图DAG不一定是树;“箭头画向下”也不是判断任意图无环的充分形式定义。理解遍历需依结构和边的关系,不靠纸面朝向。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 5.3 堆栈
原书出处 · 1 处
- 5.3 堆栈 · 查看原书依据
这被称为深度优先遍历,与之相反的是先横向遍历再向下遍历,即宽度优先遍历。每向下一层,都需要记住当前位置,这样才可以回去。回去之后,就不需要再记得那个位置了。 我们需要的是像自助餐厅里能堆盘子的小工具一样的事物。当调用一个函数时,将返回地址贴在一个盘子上,并将其放在堆的顶部。当从函
参考来源
- 位置:《计算机系统解密》5.3 堆栈(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0049.html)
- 结论依据:5.3展开向下/横向与返回,纠正树等同任意DAG及箭头方向论证的简化。
- 原始内容:这被称为深度优先遍历,与之相反的是先横向遍历再向下遍历,即宽度优先遍历。每向下一层,都需要记住当前位置,这样才可以回去。回去之后,就不需要再记得那个位置了。 我们需要的是像自助餐厅里能堆盘子的小工具一样的事物。当调用一个函数时,将返回地址贴在一个盘子上,并将其放在堆的顶部。当从函