二叉树——二叉树先序、中序和后续遍历

Posted on | In ,

任何一个二叉树，都可以由它的先序和中序遍历唯一确定。

任何一个二叉树，都可以有它的中序和后序遍历唯一确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 使用递归先序遍历
public static void preOrderRecur(TreeNode root) {
	if (root == null) {
		return;
	}
	System.out.println(root.data + " ");
	preOrderRecur(root.left);
	preOrderRecur(root.right);
}
// 使用递归中序遍历
public static void preOrderRecur(TreeNode root) {
	if (root == null) {
		return;
	}
	preOrderRecur(root.left);
	System.out.println(root.data + " ");
	preOrderRecur(root.right);
}
// 使用递归后序遍历
public static void preOrderRecur(TreeNode root) {
	if (root == null) {
		return;
	}
	preOrderRecur(root.left);
	preOrderRecur(root.right);
	System.out.println(root.data + " ");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Stack;
/*
 * 使用递归和循环进行先序遍历
 */
public class PreOrder {
	// 使用递归遍历
	public static void preOrderRecur(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.data + " ");
		preOrderRecur(root.left);
		preOrderRecur(root.right);
	}
	// 使用循环遍历
	public void preOrderUnrecur(TreeNode root) {
		if (root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			root = stack.pop();
			System.out.print(root.data + " ");
			if (root.right != null) {
				stack.push(root.right);
			}
			if (root.right != null) {
				stack.push(root.left);
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
// Test
public static void main(String[] args) {
	TreeNode node1 = new TreeNode(1);
	TreeNode node2 = new TreeNode(2);
	TreeNode node3 = new TreeNode(3);
	TreeNode node4 = new TreeNode(4);
	TreeNode node5 = new TreeNode(5);
	node1.left = node2;
	node1.right = node3;
	node2.left = node4;
	node2.right = node5;
	preOrderRecur(node1);
}