二叉树的遍历

一、相关概念

二叉树可以说是树的一个变种,与树的区别就在于二叉树的度数要么为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个位置:_ _ _
    • 确定“中”的位置,前序的“中”在最前,中序的“中”在中间,后序的“中”在末尾(如中序:_ 中 _)
    • 剩下的位置从左到右依次填入“左”、“右”即可(如中序:左 中 右)
  • 对于层次遍历:
    • 从上到下一行一行开始遍历,每行从左到右遍历

三、应用

本站遵循「CC BY 4.0」创作共享协议,转载请注明出处