如何用C语言实现二叉树的非递归遍历算法？

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

目录

一、二叉树的前序遍历

二、二叉树的中序遍历

三、二叉树的后序遍历

3.1 方法一

3.2 方法二

一、二叉树的前序遍历：遍历顺序为根-左-右

题目链接：我们可以将任意一棵树通过前序遍历的方式转换成左子树节点和右子树节点

目录

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

一、二叉树的前序遍历

题目链接

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

解释：

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

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

当栈不为空的时候说明还有左路节点的右子树没有被访问，当cur不为空的时候说明还有树要被访问。当同时为空的时候才是访问完成。当一个节点出栈的时候说明此时该节点及该节点的左子树已经被访问完成了。