C语言实现二叉树的递归遍历和非递归遍历

本文实现了二叉树的递归遍历和非递归遍历，当然，还包括一些堆栈操作.

遍历二叉树本质上是一个堆栈和堆栈的问题. 递归算法简单易懂，但效率始终是一个问题. 非递归算法可以清楚地知道实现的每个步骤的细节，但是乍一看并不想很好地理解递归算法，每个都有其自己的好处. 接下来，根据下图讨论树遍历.

1. 一阶遍历: 一阶遍历是首先输出根节点，然后是左子树，最后是右子树. 上图中的上一个遍历结果为: ABCDEF

2. 中阶遍历: 中阶遍历是首先输出左子树二叉树的遍历算法c实现，然后是根节点，最后是右子树. 上图中的中间序列遍历结果为: CBDAEF

3. 后序遍历: 后序遍历是先输出左子树，然后输出右子树二叉树的遍历算法c实现，最后是根节点. 上图的后遍历结果为: CDBFEA

其中，用于后序遍历的非递归算法最为复杂. 我使用了一个标识符isOut来指示是否需要弹出打印. 因为仅当打印节点的左右子树时，才能从堆栈中弹出该节点以进行打印，所以当isOut为1且isOut的初始值为0时才打印该节点，主要用于处理非叶节点. 根据后遍历的原则确定，左右子树只能由该节点打印，因此该节点肯定会被访问两次，而不是第一次打印，而第二次打印右子树. 叶子节点打印完成后，将isOut设置为1. （仔细考虑一下，应该有一个逻辑更简单的算法）

isOut的处理如下:

以有序遍历为例，查看堆栈内容如何变化:

具体代码实现如下: 请参见

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-182602-1.html