引言
前面的文章已经介绍了二叉树的递归遍历，本章介绍二叉树的非递归方式，主要是通过栈来实现，通常来讲非递归的方式在时间复杂度方面会优于递归的方式（凡事无绝对），下面介绍三种遍历方式的非递归实现
图一
一、先序遍历非递归实现
- 结点1入栈
- 出栈，输出栈顶结点1,并将1的左、右孩子结点(2和4)入栈;右孩子先入栈，左孩子后入栈，因为对左孩子的访问要先于右孩子，后入栈的会先出栈访问。
- 出栈，输出栈顶结点2,并将2的左、右孩子结点(3和5)入栈。
- 出栈，输出栈顶结点3，3为叶子结点，无孩子，本步无结点入栈
- 出栈，输出栈顶结点5
- 出栈，出栈，输出栈顶结点4
先序遍历结点进出栈过程
由此我们可得到代码
public static void preOrderNo(BTNode node) {
if (node != null) {
ArrayDeque<BTNode> stack = new ArrayDeque<>();
//根节点进栈
stack.push(node);
while (!stack.isEmpty()) {
BTNode nodeTemp = stack.pop();
System.out.print(nodeTemp.data + " ");
//右结点先入栈
if (nodeTemp.rightChild != null) {
stack.push(nodeTemp.rightChild);
}
if(nodeTemp.leftChild != null) {
stack.push(nodeTemp.leftChild);
}
}
}
}
我们可以发现，遍历的方式和层次遍历非常相像，只是层次遍历使用的是队列，而且左孩子先入队列。
二、中序遍历非递归实现
中序遍历和先序遍历有些不同，我们需先将左孩子结点全部入栈，结合中序遍历的结果来看也合理，因为第一个中序遍历的第一个元素一定是最左端的结点元素
中序遍历
- 先将左孩子入栈
- 左孩子出栈，出栈时检测有无右孩子，如果存在，则入栈
注意一开始根节点不入栈
需要注意的是在6->7步骤的过程中，栈是为空的，检测是写在循环之后的，这一点在代码中有体现，需要额外加入一个判断维持循环继续
public static void inOrderNo(BTNode node) {
if (node != null) {
ArrayDeque<BTNode> stack = new ArrayDeque<>();
BTNode p = node;
//加入p != null是因为，如图中第7步骤，当根节点出栈时，栈为空，但是循环还没有结束，
// 因为右结点4还没有添加进去，所以添加这一条件维持循环
while(!stack.isEmpty() || p != null){
//将左孩子全部入栈,需要注意的是右孩子也是通过这里入栈的
while (p != null) {
stack.push(p);
p = p.leftChild;
}
p = stack.pop();
System.out.print(p.data + " ");
p = p.rightChild;
}
}
}
三、后序遍历非递归实现
首先根据文章开头图一手工写出先序遍历和后续遍历
先序：12354
后序：35241
将后序遍历逆序得到：14253
可以发现后序不过是先序遍历过程中对左右子树遍历顺序交换所得到的结果
由此我们可以得到后序遍历的过程。
1.交换先序遍历中获取左右子树的顺序
2.实现逆序输出（使用新的一个栈即可）
实现代码：
public static void postOrderNo(BTNode node) {
if (node != null) {
ArrayDeque<BTNode> stack = new ArrayDeque<>();
ArrayDeque<BTNode> postStack = new ArrayDeque<>();
//根节点进栈
stack.push(node);
while (!stack.isEmpty()) {
BTNode nodeTemp = stack.pop();
postStack.push(nodeTemp);
//左孩子先入栈
if(nodeTemp.leftChild != null) {
stack.push(nodeTemp.leftChild);
}
if (nodeTemp.rightChild != null) {
stack.push(nodeTemp.rightChild);
}
}
//依次输出postStack即可实现逆序
while (!postStack.isEmpty()) {
BTNode postNode = postStack.pop();
System.out.print(postNode.data + " ");
}
}
}
网友评论