分别用递归和非递归方式实现二叉树先序、中序和后序遍历分别用递归和非递归方式实现

分别用递归和非递归方式实现二叉树先序、中序和后序遍历

使用java描述，读者需已经有数据结构知识
本文为代码添加了详细注释而不是抽线文字讲解

二叉树定义：

private class Node { public T value; public Node left, right; }

先序遍历遍历的顺序为“根-左-右”。
递归算法为：

public void preOrderRecurA(Node root) { // 递归算法退出条件：当前节点为空 if (root == null) { return; } // “根-左-右” System.out.println(root.value + " "); preOrderRecurA(root.left); preOrderRecurA(root.right); }

利用栈保存递归算法中间的结果。

public void preOrderRecurB(Node root) { // 开始条件为非空 if (root == null) { return; } // 栈 stack 用来保存中间节点 Stack> stack = new Stack<>(); // 算法以根结点开始 stack.push(root); // 结束条件为栈空 while (!stack.isEmpty()) { // 由“根-左-右”得知，先访问当前节点， root = stack.pop(); System.out.println(root.value); // 由于栈是先进后出，所以右孩子先入队，左孩子后入队 // 这样才能实现“根-左-右” if (root.right != null) { stack.push(root.right); } if (root.left != null) { stack.push(root.left); } } }

中序遍历遍历的顺序为“左-根-右”。
递归算法为：

public void inOrderRecurA(Node root) { // 递归算法退出条件：当前节点为空 if (root == null) { return; } // “左-根-右” inOrderRecurA(root.left); System.out.println(root.value + " "); inOrderRecurA(root.right); }

非递归算法为

public void inOrderRecurB(Node root) { // 算法运行条件：树非空 if (root == null) { return; } // 栈 stack 用来保存中间节点 Stack> stack = new Stack<>(); // 中序遍历过程中也可能栈空，退出条件需加一条 // 例如 1 // x 2 // x 为空节点，手动模拟算法便会发现遍历过程中出现了栈空 while (!stack.isEmpty() || root != null) { // 由“左-根-右”，先暂存当前元素访问左孩子 if (root != null) { stack.push(root); root = root.left; } // “左”为空，访问“根” else { root = stack.pop(); System.out.println(root.value + " "); root = root.right; } } }

后续遍历遍历的顺序为“左-右-根”。
【分别用递归和非递归方式实现二叉树先序、中序和后序遍历】递归算法为：

public void postOrderRecurA(Node root) { // 递归算法退出条件：当前节点为空 if (root == null) { return; } // “左-右-根” postOrderRecurA(root.left); postOrderRecurA(root.right); System.out.println(root.value + " "); }

非递归算法：
方法一：逆序法（两个栈）
逆后序遍历序列（后序遍历序列的逆序）只不过是把先序遍历序列过程中左右子树的顺序交换所得的结果。（自行手写某树的遍历序列就会明白）
因此只要修改一下前序遍历的算法，先保存逆后序遍历序列，再逆序输出就行了，此方法空间复杂度、时间复杂度都比较大，故不提供代码，只提供思路
方法二：难度高，手动多模拟几次

public void postOrderRecurB(Node root) { // 此算法需反复手动模拟便可理解 // 算法运行条件：树非空 if (root == null) { return; } // 栈 stack 用来保存中间节点 Stack> stack = new Stack<>(); // root 也用来表示最近一次出栈的节点 stack.push(root); // 一个临时变量，栈顶节点 Node c = null; while (!stack.isEmpty()) { c = stack.peek(); // 分三种情况 // 1.若root等于c的左孩子或右孩子，则说明c的孩子都已经打印完毕（“左-右-根”）， // 否则则说明左孩子尚未遍历 if (c.left != null && root != c.left && root != c.right) { stack.push(c.left); } // 2.当条件1不成立时且root不为c的右孩子时（右孩子存在），则说明“左”已经遍历，该访问“右” else if (c.right != null && root != c.right) { stack.push(c.right); // 3.“左-右”都遍历完毕，访问根节点 } else { System.out.println(stack.pop().value + " "); // 注意：记录这次出栈的节点 root = c; } } }