如何详细解析非递归实现二叉树遍历算法？

本文共计1120个文字，预计阅读时间需要5分钟。

目录

1.二叉树的前序遍历

2.二叉树的中序遍历

3.二叉树的后序遍历

3.1 方法一

3.2 方法二

一、二叉树的前序遍历

题目链接我们可以把任何一棵树看成一个左子树和右子树的组合，二叉树的前序遍历是先访问根节点，然后递归地访问左子树和右子树。

目录

• 一、二叉树的前序遍历
• 二、二叉树的中序遍历
• 三、二叉树的后序遍历
• 3.1 方法一
• 3.2 方法二

一、二叉树的前序遍历

题目链接

我们可以把任何一棵树看成左路节点，左路节点和右子树。先访问左路节点，再访问左路节点的右子树。在右子树中也重复这种循环，就是非递归遍历二叉树的思想。

解释：

栈st存放节点，v存放数值，cur初始化为root。

循环条件是栈不为空或者cur不为空(访问最后一个节点之前栈就已经为空了)，循环遍历左子树并且把左子树入栈，同时把值存入v中。然后弹出栈顶元素，并且把栈顶元素的右子树赋值给cur，这样就形成了遍历。

当栈不为空的时候说明还有左路节点的右子树没有被访问，当cur不为空的时候说明还有树要被访问。当同时为空的时候才是访问完成。