C-数据结构-树的遍历

树的遍历

• 什么是遍历

  按某条搜索路线遍访每个节点且不重复(又称周游)

  遍历二叉树: 从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个节点均被访问一次且仅被访问一次

• 作用

  它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。

前序遍历

• 若二叉树为空,则空操作;否则

  • 访问 根节点
  • 前序遍历左子树
  • 前序遍历右子树

• 特点: 第一位一定是根节点

• 记忆: 根-左-右

• 结果

  

• 演示动画

  

中序遍历

• 若二叉树为空，则空操作;否则

  • 中序遍历左子树
  • 访问 根节点
  • 中序遍历 右子树

• 特点: 根节点必在中间

• 记忆:左-根-右

• 结果

  

• 演示动画

  

后序遍历

• 若二叉树为空,则空操作；否则

• 后续遍历左子树
• 后续遍历右子树
• 访问根节点
• 特点: 最后一位一定是 根节点

• 记忆: 左-右-根

• 结果

  

• 演示动画

  

内容是学习后整理与哔哩哔哩视频,原"老九学堂 C-数据结构"