二叉树的先序遍历

马谦马谦马谦 数据结构和算法评论205字数 520阅读1分44秒阅读模式

一、先序遍历

先序遍历的意思是:先遍历当前节点,再分别遍历左、右子节点。

例如一棵二叉树为:

二叉树的先序遍历-图片1

它的先序遍历序列(红色虚线标出来的)为:[1, 2, 4, 3, 5 6]。

二、递归实现

递归的实现很简单,先访问当前节点,然后分别递归访问左右子节点。

三、非递归实现

非递归的方式依赖栈来实现,逻辑:

  1. 访问根节点,把当前节点压栈。然后设置当前节点为左子节点,重复过程,直到左子节点为空。
  2. 设置当前节点为栈顶节点的右子节点,重复1过程。

3.1 图文描述

以上面的二叉树为例,首先访问根元素1,压栈:

二叉树的先序遍历-图片2

然后继续访问1节点的左节点2,压栈:

二叉树的先序遍历-图片3

节点2没有左子节点,退出左树遍历。然后取出栈顶元素2,访问它的右子节点4:

二叉树的先序遍历-图片4

右子节点没有子节点,因此继续从栈顶取元素1,访问它的右子节点3并压栈:

二叉树的先序遍历-图片5

节点3有左子节点,顺着遍历左子节点5,节点5入栈:

二叉树的先序遍历-图片6

此时5没有没有左子节点了,于是取出栈顶元素5,访问它的右子节点。但是它没有右子节点,继续取出栈顶元素3,访问它的右子节点6:

二叉树的先序遍历-图片7

访问完6后,因为没有子节点了。所以继续从栈里取元素,但是此时栈也为空了,遍历结束。

3.2 代码描述

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020年2月8日17:29:53
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/pre-order-traversal-in-binary-trees.html
二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

一、后序遍历 后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。 一个后序遍历的示例,它的后序遍历结果为[4, 2, 5, 6, 3, 1]: 二、非递归实现 后序遍历的非递归实现比前序和中序的非...
二叉树的中序遍历 数据结构和算法

二叉树的中序遍历

一、中序遍历 中序遍历过程:先访问左子节点,然后访问当前节点,最后访问右子节点。 以下试一次中序遍历过程: 二、非递归实现 非递归方式遍历依赖栈来实现,因为要先访问子节点,然后访问父节点,因此必须要有...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证