0%

二叉树的遍历

一、相关概念

二叉树可以说是树的一个变种,与树的区别就在于二叉树的度数要么为 0,要么为 2

性质

在二叉树中,有这样几个性质(来自一本通):

  • 第 i 层最多有 2i – 1 个结点(i >= 1)
  • k 深度的二叉树最多有 2k – 1 结点(k >= 1)
  • 叶结点(root)结点数为 n0,度数为 2 的结点数为 n2,n0 = n2 + 1
  • n 个结点的完全二叉树深度为 floor(log2n) + 1

二、遍历

有这样一棵二叉树

现在让你求这棵树的先序、中序、后序以及层次遍历

先序遍历

如果二叉树为空,则空操作,否则:

  1. 访问根结点
  2. 先序遍历左子树
  3. 先序遍历右子树

换句话说,就是:根结点 -> 左结点 -> 右结点(中左右)

在这棵二叉树中,对应的结果为:ABDEGHCF

中序遍历

如果二叉树为空,则空操作,否则:

  1. 中序遍历左子树
  2. 访问根结点
  3. 中序遍历右子树

换句话说,就是:左结点 -> 根结点 -> 右结点(左中右)

在这棵二叉树中,对应的结果为:DBGEHACF

后序遍历

如果二叉树为空,则空操作,否则:

  1. 后序遍历左子树
  2. 后序遍历右字数
  3. 访问根结点

换句话说,就是:左结点 -> 右结点 -> 根结点(左右中)

在这棵二叉树中,对应的结果为:DGHEBFCA

层次遍历

从上到下一行一行,每行从左到右,如下图

在这棵二叉树中,对应的结果为:ABCDEFGH

记忆方法

  • 对于先序,中序,后序遍历:
    • 留3个位置:_ _ _
    • 确定“中”的位置,先序的“中”在最前,中序的“中”在中间,后序的“中”在末尾(如先序:中 □ □,中序:□ 中 □,后序:□ □ 中)
    • 剩下的位置从左到右依次填入“左”、“右”即可(如先序:中 左 右,中序:左 中 右,后序:左 右 中)
  • 对于层次遍历:
    • 从上到下一行一行开始遍历,每行从左到右遍历

三、应用

  • 本文作者: rcxzsc
  • 本文链接: https://rcxzsc.com/archives/773/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY 许可协议。转载请注明出处!