左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）

程序员文章站 2022-06-28 18:22:36

本题来自左神《程序员代码面试指南》“分别用递归和非递归方式实现二叉树先序、中序和后序遍历”题目。题目用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。二叉树节点定义如下：public static class Node {public int value;public Node left;public Node right;public Node(int data....

本题来自左神《程序员代码面试指南》“分别用递归和非递归方式实现二叉树先序、中序和后序遍历”题目。

题目

用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。

我们约定：

先序遍历顺序为根、左、右；
中序遍历顺序为左、根、右；
后序遍历顺序为左、右、根。

二叉树节点定义如下：

public static class Node {
	public int value;
	public Node left;
	public Node right;

	public Node(int data) {
		this.value = data;
	}
}

题解

1、用递归方式

用递归方式实现三种遍历是教材上的基础内容，本文不再详述，直接给出代码实现。

// 前序遍历
public static void preOrderRecur(Node head) {
	if (head == null) {
		return;
	}
	System.out.print(head.value + " ");
	preOrderRecur(head.left);
	preOrderRecur(head.right);
}

// 中序遍历
public static void inOrderRecur(Node head) {
	if (head == null) {
		return;
	}
	inOrderRecur(head.left);
	System.out.print(head.value + " ");
	inOrderRecur(head.right);
}

// 后序遍历
public static void posOrderRecur(Node head) {
	if (head == null) {
		return;
	}
	posOrderRecur(head.left);
	posOrderRecur(head.right);
	System.out.print(head.value + " ");
}

2、用非递归方式

（1）前序遍历

用递归方法解决的问题都能用非递归的方法实现。这是因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。用非递归的方式实现二叉树的先序遍历，具体过程如下：

1．申请一个新的栈，记为stack。然后将头节点head 压入stack 中。
2．从 stack 中弹出栈顶节点，记为 cur，然后打印 cur 节点的值，再将节点cur 的右孩子节点（不为空的话）先压入stack 中，最后将cur 的左孩子节点（不为空的话）压入stack 中。
3．不断重复步骤2，直到 stack 为空，全部过程结束。

下面举例说明整个过程，一棵二叉树如图 3-1 所示：
左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）
节点 1 先入栈，然后弹出并打印。接下来先把节点3 压入stack，再把节点2 压入，stack从栈顶到栈底依次为 2，3。
节点 2 弹出并打印，把节点5 压入stack，再把节点4 压入，stack 从栈顶到栈底为 4，5，3。
节点 4 弹出并打印，节点4 没有孩子节点压入stack，stack 从栈顶到栈底依次为 5，3。
节点 5 弹出并打印，节点5 没有孩子节点压入stack，stack 从栈顶到栈底依次为 3。
节点 3 弹出并打印，把节点7 压入stack，再把节点6 压入，stack 从栈顶到栈底为 6，7。
节点 6 弹出并打印，节点6 没有孩子节点压入stack，stack 目前从栈顶到栈底为 7。
节点 7 弹出并打印，节点7 没有孩子节点压入stack，stack 已经为空，过程停止。

整个过程请参看如下代码中的 preOrderUnRecur 方法。

public static void preOrderUnRecur(Node head) {
	System.out.print("pre-order: ");
	if (head != null) {
		Stack<Node> stack = new Stack<Node>();
		stack.add(head);
		while (!stack.isEmpty()) {
			head = stack.pop(); // 弹出栈顶元素
			System.out.print(head.value + " ");
			if (head.right != null) { // 左子树进栈
				stack.push(head.right);
			}
			if (head.left != null) { // 右子树进栈
				stack.push(head.left);
			}
		}
	}
	System.out.println();
}

（2）中序遍历

用非递归的方式实现二叉树的中序遍历，具体过程如下：

1．申请一个新的栈，记为 stack。初始时，令变量 cur=head。
2．先把 cur 节点压入栈中，对以 cur 节点为头节点的整棵子树来说，依次把左边界压入栈中，即不停地令 cur=cur.left，然后重复步骤 2。
3．不断重复步骤2，直到发现 cur 为空，此时从 stack 中弹出一个节点，记为 node。打印 node 的值，并且让 cur=node.right，然后继续重复步骤 2。
4．当 stack 为空且 cur 为空时，整个过程停止。

还是用图 3-1 的例子来说明整个过程。
左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）
初始时 cur 为节点1，将节点1 压入stack，令cur=cur.left，即cur 变为节点2。（步骤1+步骤2）
cur 为节点2，将节点2 压入stack，令cur=cur.left，即cur 变为节点4。（步骤2）
cur 为节点4，将节点4 压入stack，令cur=cur.left，即cur 变为null，此时stack 从栈顶到栈底为4，2，1。（步骤2）
cur 为null，从stack 弹出节点4（node）并打印，令cur=node.right，即cur 为null，此时stack 从栈顶到栈底为2，1。（步骤3）
cur 为null，从stack 弹出节点2（node）并打印，令cur=node.right，即cur 变为节点5，此时stack 从栈顶到栈底为1。（步骤3）
cur 为节点5，将节点5 压入stack，令cur=cur.left，即cur 变为null，此时stack 从栈顶到栈底为5，1。（步骤2）
cur 为null，从stack 弹出节点5（node）并打印，令cur=node.right，即cur 仍为null，此时stack 从栈顶到栈底为1。（步骤3）
cur 为null，从stack 弹出节点1（node）并打印，令cur=node.right，即cur 变为节点3，此时stack 为空。（步骤3）
cur 为节点3，将节点3 压入stack，令cur=cur.left，即cur 变为节点6，此时stack 从栈顶到栈底为3。（步骤2）
cur 为节点6，将节点6 压入stack，令cur=cur.left，即cur 变为null，此时stack 从栈顶到栈底为6，3。（步骤2）
cur 为null，从stack 弹出节点6（node）并打印，令cur=node.right，即cur 仍为null，此时stack 从栈顶到栈底为3。（步骤3）
cur 为null，从stack 弹出节点3（node）并打印，令cur=node.right，即cur 变为节点7，此时stack 为空。（步骤3）
cur 为节点7，将节点7 压入stack，令cur=cur.left，即cur 变为null，此时stack 从栈顶到栈底为7。（步骤2）
cur 为null，从stack 弹出节点7（node）并打印，令cur=node.right，即cur 仍为null，此时stack 为空。（步骤3）
cur 为null，stack 也为空，整个过程停止。（步骤4）

通过与例子结合的方式我们发现，步骤1 到步骤4 就是依次先打印左子树，然后打印每棵子树的头节点，最后打印右子树。
全部过程请参看如下代码中的 inOrderUnRecur 方法。

public static void inOrderUnRecur(Node head) {
	System.out.print("in-order: ");
	if (head != null) {
		Stack<Node> stack = new Stack<Node>();
		while (!stack.isEmpty() || head != null) {
			if (head != null) { // 如果向左没走到头，则不断向左走，并将遍历过的元素入栈
				stack.push(head);
				head = head.left;
			} else { // 如果向左走到头了，则出栈一个元素，然后将其右孩子入栈
				head = stack.pop();
				System.out.print(head.value + " ");
				head = head.right;
			}
		}
	}
	System.out.println();
}

（3）后序遍历

用非递归的方式实现二叉树的后序遍历有点麻烦，本书介绍以下两种方法供读者参考。

先介绍用 两个栈 实现后序遍历的过程，具体过程如下：

1．申请一个栈，记为 s1，然后将头节点 head 压入s1 中。
2．从 s1 中弹出的节点记为 cur，然后依次将 cur 的 左孩子节点 和 右孩子节点 压入 s1 中。
3．在整个过程中，每一个从 s1 中弹出的节点都放进 s2 中。
4．不断重复 步骤2 和 步骤3，直到 s1 为空，过程停止。
5．从 s2 中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。

还是用图3-1 的例子来说明整个过程。
左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）
节点 1 放入 s1 中。
从 s1 中弹出节点1，节点1 放入s2，然后将节点2 和节点3 依次放入s1，此时s1 从栈顶到栈底为3，2；s2 从栈顶到栈底为1。
从 s1 中弹出节点3，节点3 放入s2，然后将节点6 和节点7 依次放入s1，此时s1 从栈顶到栈底为7，6，2；s2 从栈顶到栈底为3，1。
从 s1 中弹出节点7，节点7 放入s2，节点7 无孩子节点，此时s1 从栈顶到栈底为6，2；s2 从栈顶到栈底为7，3，1。
从 s1 中弹出节点6，节点6 放入s2，节点6 无孩子节点，此时s1 从栈顶到栈底为2；s2从栈顶到栈底为6，7，3，1。
从 s1 中弹出节点2，节点2 放入s2，然后将节点4 和节点5 依次放入s1，此时s1 从栈顶到栈底为5，4；s2 从栈顶到栈底为2，6，7，3，1。
从 s1 中弹出节点5，节点5 放入s2，节点5 无孩子节点，此时s1 从栈顶到栈底为4；s2从栈顶到栈底为5，2，6，7，3，1。
从 s1 中弹出节点4，节点4 放入s2，节点4 无孩子节点，此时s1 为空；s2 从栈顶到栈底为4，5，2，6，7，3，1。

过程结束，此时只要依次弹出s2 中的节点并打印即可，顺序为4，5，2，6，7，3，1。
通过如上过程我们知道，每棵子树的头节点都最先从 s1 中弹出，然后把该节点的孩子节点按照先左再右的顺序压入 s1，那么从 s1 弹出的顺序就是先右再左，所以从 s1 中弹出的顺序就是中、右、左。然后，s2 重新收集的过程就是把 s1 的弹出顺序逆序，所以 s2 从栈顶到栈底的顺序就变成了左、右、中。

使用两个栈实现后序遍历的全部过程请参看如下代码中的 posOrderUnRecur1 方法。

public static void posOrderUnRecur1(Node head) {
	System.out.print("pos-order: ");
	if (head != null) {
		Stack<Node> s1 = new Stack<Node>();
		Stack<Node> s2 = new Stack<Node>();
		s1.push(head);
		while (!s1.isEmpty()) {
			head = s1.pop();
			s2.push(head); // 每一个从 s1 中弹出的节点都放进 s2 中
			if (head.left != null) {
				s1.push(head.left); // 将 cur 的左孩子节点压入 s1 中
			}
			if (head.right != null) {
				s1.push(head.right); // 将 cur 的右孩子节点压入 s1 中
			}
		}
		while (!s2.isEmpty()) { // 从 s2 中依次弹出节点并打印
			System.out.print(s2.pop().value + " ");
		}
	}
	System.out.println();
}

最后介绍只用一个栈实现后序遍历的过程，具体过程如下。

1．申请一个栈，记为 stack，将头节点压入 stack，同时设置两个变量 h 和 c。在整个流程中，h 代表最近一次弹出并打印的节点，c 代表 stack 的栈顶节点，初始时 h 为头节点，c 为 null。

2．每次令 c 等于当前 stack 的栈顶节点，但是不从 stack 中弹出，此时分以下三种情况。

① 如果 c 的左孩子节点不为null，并且 h 不等于 c 的左孩子节点，也不等于 c 的右孩子节点，则把 c 的左孩子节点压入 stack 中。
（具体解释一下这么做的原因。首先 h 的意义是最近一次弹出并打印的节点，且后续遍历的打印顺序是“左-中-右”，所以，如果 h 等于 c 的左孩子节点，说明 c 的左子树已经打印完毕；如果 h 等于 c 的右孩子节点，说明 c 的左子树与右子树都已经打印完毕。所以无论 h 等于 c 的左孩子节点还是右孩子节点，此时都不应该再将 c 的左孩子节点放入 stack 中。否则，说明左子树还没处理过，那么将 c 的左孩子节点压入 stack 中。）
② 如果条件①不成立，并且 c 的右孩子节点不为 null，h 不等于 c 的右孩子节点，则把 c 的右孩子节点压入 stack 中。
（具体解释一下这么做的原因。如果 h 等于 c 的右孩子节点，说明 c 的右子树已经打印完毕，此时不应该再将 c 的右孩子节点放入 stack 中。否则，说明右子树还没处理过，此时将 c 的右孩子节点压入 stack 中。）
③ 如果条件①和条件②都不成立，说明 c 的左子树和右子树都已经打印完毕，那么从 stack 中弹出 c 并打印，然后令 h=c。

3．一直重复步骤2，直到 stack 为空，过程停止。

依然用图 3-1 的例子来说明整个过程。
左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）

节点 1 压入stack，初始时h 为节点1，c 为null，stack 从栈顶到栈底为1。
令c 等于stack 的栈顶节点——节点1，此时步骤2 的条件①命中，将节点2 压入stack，h为节点1，stack 从栈顶到栈底为2，1。
令c 等于stack 的栈顶节点——节点2，此时步骤2 的条件①命中，将节点4 压入stack，h为节点1，stack 从栈顶到栈底为4，2，1。
令c 等于stack 的栈顶节点——节点4，此时步骤2 的条件③命中，将节点4 从stack 中弹出并打印，h 变为节点4，stack 从栈顶到栈底为2，1。
令c 等于stack 的栈顶节点——节点2，此时步骤2 的条件②命中，将节点5 压入stack，h为节点4，stack 从栈顶到栈底为5，2，1。
令c 等于stack 的栈顶节点——节点5，此时步骤2 的条件③命中，将节点5 从stack 中弹出并打印，h 变为节点5，stack 从栈顶到栈底为2，1。
令c 等于stack 的栈顶节点——节点2，此时步骤2 的条件③命中，将节点2 从stack 中弹出并打印，h 变为节点2，stack 从栈顶到栈底为1。
令c 等于stack 的栈顶节点——节点1，此时步骤2 的条件②命中，将节点3 压入stack，h为节点2，stack 从栈顶到栈底为3，1。
令c 等于stack 的栈顶节点——节点3，此时步骤2 的条件①命中，将节点6 压入stack，h为节点2，stack 从栈顶到栈底为6，3，1。
令c 等于stack 的栈顶节点——节点6，此时步骤2 的条件③命中，将节点6 从stack 中弹出并打印，h 变为节点6，stack 从栈顶到栈底为3，1。
令c 等于stack 的栈顶节点——节点3，此时步骤2 的条件②命中，将节点7 压入stack，h为节点6，stack 从栈顶到栈底为7，3，1。
令c 等于stack 的栈顶节点——节点7，此时步骤2 的条件③命中，将节点7 从stack 中弹出并打印，h 变为节点7，stack 从栈顶到栈底为3，1。
令c 等于stack 的栈顶节点——节点3，此时步骤2 的条件③命中，将节点3 从stack 中弹出并打印，h 变为节点3，stack 从栈顶到栈底为1。
令c 等于stack 的栈顶节点——节点1，此时步骤2 的条件③命中，将节点1 从stack 中弹出并打印，h 变为节点1，stack 为空。过程结束。

只用一个栈实现后序遍历的全部过程请参看如下代码中的 posOrderUnRecur2 方法。

public static void posOrderUnRecur2(Node h) {
	System.out.print("pos-order: ");
	if (h != null) { // h 代表最近一次弹出并打印的节点
		Stack<Node> stack = new Stack<Node>();
		stack.push(h);
		Node c = null; // c 代表 stack 的栈顶节点
		while (!stack.isEmpty()) {
			c = stack.peek();
			if (c.left != null && h != c.left && h != c.right) { // 说明 c 的左子树还没处理过
				stack.push(c.left);
			} else if (c.right != null && h != c.right) { // 说明 c 的右子树还没处理过
				stack.push(c.right);
			} else { // 说明 c 的左子树和右子树都已经打印完毕
				System.out.print(stack.pop().value + " ");
				h = c;
			}
		}
	}
	System.out.println();
}

附：完整代码（含测试用例）

package chapter_3_binarytreeproblem;

import java.util.Stack;

public class Problem_01_PreInPosTraversal {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void preOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
	}

	public static void inOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		inOrderRecur(head.left);
		System.out.print(head.value + " ");
		inOrderRecur(head.right);
	}

	public static void posOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		posOrderRecur(head.left);
		posOrderRecur(head.right);
		System.out.print(head.value + " ");
	}

	public static void preOrderUnRecur(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.add(head);
			while (!stack.isEmpty()) {
				head = stack.pop(); // 弹出栈顶元素
				System.out.print(head.value + " ");
				if (head.right != null) { // 左子树进栈
					stack.push(head.right);
				}
				if (head.left != null) { // 右子树进栈
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}

	public static void inOrderUnRecur(Node head) {
		System.out.print("in-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || head != null) {
				if (head != null) { // 如果向左没走到头，则不断向左走，并将遍历过的元素入栈
					stack.push(head);
					head = head.left;
				} else { // 如果向左走到头了，则出栈一个元素，然后将其右孩子入栈
					head = stack.pop();
					System.out.print(head.value + " ");
					head = head.right;
				}
			}
		}
		System.out.println();
	}

	public static void posOrderUnRecur1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
				head = s1.pop();
				s2.push(head); // 每一个从 s1 中弹出的节点都放进 s2 中
				if (head.left != null) {
					s1.push(head.left); // 将 cur 的左孩子节点压入 s1 中
				}
				if (head.right != null) {
					s1.push(head.right); // 将 cur 的右孩子节点压入 s1 中
				}
			}
			while (!s2.isEmpty()) { // 从 s2 中依次弹出节点并打印
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

	public static void posOrderUnRecur2(Node h) {
		System.out.print("pos-order: ");
		if (h != null) { // h 代表最近一次弹出并打印的节点
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null; // c 代表 stack 的栈顶节点
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && h != c.left && h != c.right) { // 说明 c 的左子树还没处理过
					stack.push(c.left);
				} else if (c.right != null && h != c.right) { // 说明 c 的右子树还没处理过
					stack.push(c.right);
				} else { // 说明 c 的左子树和右子树都已经打印完毕
					System.out.print(stack.pop().value + " ");
					h = c;
				}
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head = new Node(5);
		head.left = new Node(3);
		head.right = new Node(8);
		head.left.left = new Node(2);
		head.left.right = new Node(4);
		head.left.left.left = new Node(1);
		head.right.left = new Node(7);
		head.right.left.left = new Node(6);
		head.right.right = new Node(10);
		head.right.right.left = new Node(9);
		head.right.right.right = new Node(11);

		// recursive
		System.out.println("==============recursive==============");
		System.out.print("pre-order: ");
		preOrderRecur(head);
		System.out.println();
		System.out.print("in-order: ");
		inOrderRecur(head);
		System.out.println();
		System.out.print("pos-order: ");
		posOrderRecur(head);
		System.out.println();

		// unrecursive
		System.out.println("============unrecursive=============");
		preOrderUnRecur(head);
		inOrderUnRecur(head);
		posOrderUnRecur1(head);
		posOrderUnRecur2(head);
	}
}

运行结果：

==============recursive==============
pre-order: 5 3 2 1 4 8 7 6 10 9 11 
in-order: 1 2 3 4 5 6 7 8 9 10 11 
pos-order: 1 2 4 3 6 7 9 11 10 8 5 
============unrecursive=============
pre-order: 5 3 2 1 4 8 7 6 10 9 11 
in-order: 1 2 3 4 5 6 7 8 9 10 11 
pos-order: 1 2 4 3 6 7 9 11 10 8 5 
pos-order: 1 2 4 3 6 7 9 11 10 8 5

本文地址：https://blog.csdn.net/sinat_42483341/article/details/111054049