欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(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