二叉树的先序遍历

有空一起学习 2020年2月8日17:29:53 发表评论
文章最后编辑于:2020-2-8 17:31:53

一、先序遍历

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

例如一棵二叉树为:

二叉树的先序遍历

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

二、递归实现

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

三、非递归实现

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

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

3.1 图文描述

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

二叉树的先序遍历

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

二叉树的先序遍历

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

二叉树的先序遍历

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

二叉树的先序遍历

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

二叉树的先序遍历

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

二叉树的先序遍历

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

3.2 代码描述

本文共执行66次查询,耗时0.389秒!
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: