二叉树的先序遍历

2020年2月8日 评论

一、先序遍历

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

例如一棵二叉树为:

二叉树的先序遍历

它的先序遍历序列(红色虚线标出来的)为:[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 代码描述

二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

一、后序遍历 后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。 一个后序遍历的示例,它的后序遍历结果为: 二、非递归实现 后序遍历的非递归实现比前序和中序的非递归实现要复杂很多,因为每个节点都可...
二叉树的中序遍历 数据结构和算法

二叉树的中序遍历

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

发表评论

匿名网友