树和森林的遍历

树的遍历

树的遍历是指：按某种方式访问树中每个结点，且每个结点只访问一次。

主要讲两种：

• 先根遍历

  • 先访问根结点
  • 再依次遍历根结点的每棵子树
  • 规律：先根后子树

• 后根遍历

  • 先依次遍历根结点的每棵子树
  • 最后访问根结点
  • 规律：先子树后根

树的遍历与二叉树的对应关系

• 树的先根遍历序列 = 对应二叉树的先序遍历序列
• 树的后根遍历序列 = 对应二叉树的中序遍历序列

这个对应关系非常重要，常考。

森林的遍历

基于“森林和树相互递归”的定义，森林有两种遍历方法。

• 先序遍历森林

  • 访问森林中第一棵树的根结点
  • 先序遍历第一棵树中根结点的子树森林
  • 先序遍历除去第一棵树后的剩余森林

• 后序遍历森林

  • 后序遍历第一棵树后根结点的子树森林
  • 访问第一棵树的根结点
  • 后序遍历除去第一棵树后的剩余森林

森林的遍历与二叉树的对应关系

• 森林的先序遍历 = 对应二叉树的先序遍历
• 森林的后序遍历 = 对应二叉树的中序遍历

这一节最该背的结论

• 树：

  • 先根遍历
  • 后根遍历

• 森林：

  • 先序遍历
  • 后序遍历

• 对应关系：

  • 树的先根遍历 ↔ 二叉树的先序遍历
  • 树的后根遍历 ↔ 二叉树的中序遍历
  • 森林的先序遍历 ↔ 二叉树的先序遍历
  • 森林的后序遍历 ↔ 二叉树的中序遍历

内容也比较简单，几分钟就搞定了。
本来是想继续往下看哈夫曼树的，
但是好累啊，头脑发昏了。
还是明天再说吧，洗个澡睡觉了。