知识卡片
遍历次序决定何时访问根
把每个节点看成一棵子树的根,三种深度遍历只改变访问根的时机:先序为根—左子树—右子树,中序为左子树—根—右子树,后序为左子树—右子树—根。递归处理的是整个子树,不是只看左右两个孩子便结束。
层级遍历按层从上向下、同层从左向右访问,是广度优先顺序。02838同一树的结果为:
| 遍历 | 节点顺序 |
|---|---|
| 先序 | 20,9,5,15,11,53,79 |
| 中序 | 5,9,11,15,20,53,79 |
| 后序 | 5,11,15,9,79,53,20 |
| 层级 | 20,9,53,5,15,79,11 |
表按图中箭头/树关系核对,未运行遍历代码。一般二叉树的中序不保证按值递增,只有额外键序约束才提供这一性质。
157三个函数的意图是以根数据入链的位置实现先/中/后序,list要先初始化。实际孩子判断错误已单列;不能把文本预期序列说成这些原函数已生成的输出。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
先序遍历、中序遍历、后序遍历以及层级遍历。本章后面介绍的关于表达式树的例子就采用了先序、中序和后序遍历的递归实现。现在让我们看看每种周游算法都是如何工作的。 如果我们把一棵树按照递归的思路想象成许多更小的子树集合,那么遍历一棵树就变得非常简单了。图9-3展示了每种周游算法的遍历顺序。尽管这里只是在二
- · 查看原书依据
按照访问结点的顺序把它们加入链表list中。当首个递归调用最终返回时,list就包含分别按照前序、中序和后序方式遍历的结点。请注意递归实现这些遍历方式是多么完美地为本章前面介绍的定义建模。 示例9-3:遍历二叉树的实现函数
参考来源
- 位置:《算法精解:C语言描述》第9章《二叉树介绍》(spine1286;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1253.html;u145-ch09-005)。
- 结论依据:145四种完整解释与02838四组图实读,逐项保留含11的深层访问位置,非仅复述名字。
- 原始内容:先序遍历、中序遍历、后序遍历以及层级遍历。本章后面介绍的关于表达式树的例子就采用了先序、中序和后序遍历的递归实现。现在让我们看看每种周游算法都是如何工作的。 如果我们把一棵树按照递归的思路想象成许多更小的子树集合,那么遍历一棵树就变得非常简单了。图9-3展示了每种周游算法的遍历顺序。尽管这里只是在二
- 位置:《算法精解:C语言描述》第9章《二叉树示例:表达式处理》(spine1296;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1263.html;u157-ch09-005)。
- 结论依据:157三个函数的意图是以根数据入链的位置实现先/中/后序,list要先初始化。实际孩子判断错误已单列;不能把文本预期序列说成这些原函数已生成的输出。
- 原始内容:按照访问结点的顺序把它们加入链表list中。当首个递归调用最终返回时,list就包含分别按照前序、中序和后序方式遍历的结点。请注意递归实现这些遍历方式是多么完美地为本章前面介绍的定义建模。 示例9-3:遍历二叉树的实现函数