二叉树的遍历是数据结构这门课中一个很基础的要求，通常我们会使用递归的方式来遍历二叉树，递归也比较利于理解。
而对于二叉树的非递归遍历，通常我们采用栈的方式实现。下面就分别说一下如何使用栈来实现二叉树的先序、中序、后序遍历。
首先给出二叉树的数据结构：
public class TreeNode {
private String value;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode() {}
public TreeNode(String value) {
this.value = value;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Boolean hasLeftChild() {
return leftChild != null;
}
public Boolean hasRightChild() {
return rightChild != null;
}
public void setLeftChild(TreeNode node) {
this.leftChild = node;
}
public void setRightChild(TreeNode node) {
this.rightChild = node;
}
public TreeNode getLeftChild() {
return leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
}
|
先序遍历（先根遍历）
先序遍历的顺序是
简记遍历顺序就是根左右。
我们可以使用一个栈来模拟这个访问过程：
- 先将根节点入栈
- 然后弹出栈顶元素并打印
- 然后将右孩子入栈，再将左孩子入栈（注意顺序），然后转到第二步，直到栈中元素为空。
转换成代码很简单
public void preOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode top = stack.pop();
System.out.print(top.getValue());
if (top.hasRightChild()) {
stack.push(top.getRightChild());
}
if (top.hasLeftChild()) {
stack.push(top.getLeftChild());
}
}
}
|
后序遍历（后根遍历）
后序遍历的顺序是：
简记遍历顺序就是左右根。
回想一下先序遍历的顺序，根左右，如果我们把左右子树入栈的顺序变换一下，那么遍历的顺序就变成了根右左，然后我们在之前打印的时候不执行打印操作，而是改为将要打印的元素再压入一个新的栈里，然后再依次将元素出栈打印，那不就得到了我们想要的后序遍历的顺序左右根吗？
按照这个想法，我们将上面的代码可以修改为：
public void postOrder(TreeNode root) {
Stack<TreeNode> preOrderStack = new Stack<>();
Stack<TreeNode> postOrderStack = new Stack<>();
preOrderStack.push(root);
while (!preOrderStack.empty()) {
TreeNode top = preOrderStack.pop();
inOrderStack.push(top);
if (top.hasLeftChild()) {
preOrderStack.push(top.getLeftChild());
}
if (top.hasRightChild()) {
preOrderStack.push(top.getRightChild());
}
}
while (!inOrderStack.empty()) {
System.out.print(inOrderStack.pop().getValue());
}
}
|
中序遍历（中根遍历）
中序遍历的顺序是：
按照这个顺序，我们可以得出以下步骤：
- 访问根节点，压栈
- 访问根节点的左孩子，继续压栈，循环这个过程，直到栈顶元素没有左孩子
- 开始处理栈中的元素，栈不为空时循环。每次弹出栈顶元素并访问之。
- 将弹出的栈顶元素的右孩子作为根节点，跳到第一步执行，直到栈内元素为空
转换成代码如下：
public void inOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode p = stack.peek().getLeftChild();
while (p != null ) {
stack.push(p);
p = p.getLeftChild();
}
while (!stack.empty()) {
TreeNode peak = stack.pop();
System.out.print(peak.getValue());
if (peak.hasRightChild()) {
stack.push(peak.getRightChild());
p = stack.peek().getLeftChild();
while (p != null ) {
stack.push(p);
p = p.getLeftChild();
}
}
}
}
|
以上就是非递归遍历二叉树的方法了，虽然代码不复杂，但还是很值得深入理解其中的思想的。
