ShiYu

# 第10节 二叉树基本算法（上）

# 二叉树

结构描述：

Class Node {
	V value;
	Node left;
	Node right;
}
1
2
3
4
5

# 二叉树的先序、中序、后序遍历

先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树 中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树 后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点

# 递归方式实现二叉树的先序、中序、后序遍历

  • 理解递归序
  • 先序、中序、后序都可以在递归序的基础上加工出来
  • 第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序

代码：

package class10;

/**
 * 	递归遍历二叉树
 * 	先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
 * 	中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
 * 	后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点
 * -理解递归序 每个节点会回到三次
 * -先序、中序、后序都可以在递归序的基础上加工出来
 * -第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序
 * @author yangyanchao
 *
 */
public class Test02_RecursiveTraversalBT {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node left;
		public Node right;
		public Node(int value) {
			this.value = value;
		}
	}
	public static void f(Node head) {
		if(head == null) {
			return;
		}
		// 1.
		f(head.left);
		// 2.
		f(head.right);
		// 3.
	}
	
	/**
	 * 	先序遍历
	 * @param head
	 */
	public static void pre(Node head) {
		if(head == null) {
			return;
		}
		System.out.print(head.value + ",");
		pre(head.left);
		pre(head.right);
	}
	
	/**
	 * 	中序遍历
	 * @param head
	 */
	public static void in(Node head) {
		if(head == null) {
			return;
		}
		in(head.left);
		System.out.print(head.value + ",");
		in(head.right);
	}
	
	/**
	 * 	后序遍历
	 * @param head
	 */
	public static void pos(Node head) {
		if(head == null) {
			return;
		}
		pos(head.left);
		pos(head.right);
		System.out.print(head.value + ",");
	}
	
	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos(head);
		System.out.println("========");
	}
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

# 非递归方式实现二叉树的先序、中序、后序遍历

  • 任何递归函数都可以改成非递归

  • 自己设计压栈的来实现

为什么要会改成非递归版本？ 因为递归实质是使用系统栈一般容量是200M左右，若递归层数很多时即使代码没有问题，也会因为系统栈容量不足，导致程序报错的 所以使用自己定义的栈就可以使用内存容量，一般生产环境一定要改写为非递归版本

代码：

package class10;

import java.util.Stack;

/**
 * 	非递归遍历二叉树
 * 	先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
 * 	中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
 * 	后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点
 * @author yangyanchao
 *
 */
public class Test03_UnRecursiveTraversalBT {
	
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public Node left;
		public Node right;
		public Node(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	非递归先序遍历二叉树
	 * 	头左右
	 * 	头节点入栈 栈弹出节点 有右入右 有左入左 
	 * @param head
	 */
	public static void preUnRecursive(Node head) {
		System.out.print("pre order: ");
		if(head == null) {
			return;
		}
		Stack<Node> stack = new Stack<Node>();
		stack.push(head);
		Node cur = null;
		while(!stack.isEmpty()) {
			cur = stack.pop();
			System.out.print(cur.value + " ");
			if(cur.right != null) {
				stack.push(cur.right);
			}
			if(cur.left != null) {
				stack.push(cur.left);
			}
		}
		System.out.println();
	}
	
	/**
	 * 	非递归中序遍历二叉树
	 * 	左头右
	 * 	1、head节点一直遍历左节点不为空则入栈，
	 * 	2、若为空则弹出栈节点打印信息并将遍历指针指向该节点的右节点然后执行1步骤
	 * @param head
	 */
	public static void inUnRecursive(Node head) {
		System.out.print("in order: ");
		if(head == null) {
			return;
		}
		Stack<Node> stack = new Stack<Node>();
		stack.push(head);
		Node cur = head.left;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.pop();
				System.out.print(cur.value + " ");
				cur = cur.right;
			}
		}
		System.out.println();
	}
	
	/**
	 * 	非递归后序遍历二叉树
	 * 	左右头 使用双栈
	 * @param head
	 */
	public static void posUnRecursive1(Node head) {
		System.out.print("pos order: ");
		if(head == null) {
			return;
		}
		Stack<Node> stack = new Stack<Node>();
		Stack<Node> printStack = new Stack<Node>();
		stack.push(head);
		Node cur = null;
		while(!stack.isEmpty()) {
			// 头 右 左
			cur = stack.pop();
			printStack.push(cur);
			if(cur.left != null) {
				stack.push(cur.left);
			}
			if(cur.right != null) {
				stack.push(cur.right);
			}
		}
		while(!printStack.isEmpty()) {
			// 左 右 头
			cur = printStack.pop();
			System.out.print(cur.value + " ");
		}
		System.out.println();
	}
	
	/**
	 * 	非递归后序遍历二叉树
	 * 	左右头 使用单栈
	 * @param head
	 */
	public static void posUnRecursive2(Node head) {
		System.out.print("pos order: ");
		if(head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(head);
			Node cur = null;
			while(!stack.isEmpty()) {
				cur = stack.peek();
				// 先入整个树的左边界然后碰到左右都null弹出(左)节点，
				// 指向上个节点入右节点然后在循着左边界入栈然后消费掉(右)节点
				// 最后消费头节点
				if(cur.left != null && head != cur.left && head != cur.right) {
					// cur.left不为空并且刚弹出的节点不是cur的左节点、右节点
					// 防止头节点的左节点再次进入stack
					stack.push(cur.left);
				} else if(cur.right != null && head != cur.right) {
					// 防止头节点的右节点再次进入stack
					stack.push(cur.right);
				} else {
					System.out.print(stack.pop().value + " ");
					head = cur;// head指向刚弹出的节点
				}
			}
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		preUnRecursive(head);
		System.out.println("========");
		inUnRecursive(head);
		System.out.println("========");
		posUnRecursive1(head);
		System.out.println("========");
		posUnRecursive2(head);
		System.out.println("========");
	}
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

# 二叉树面试证明题

X 祖先节点 交集 先序（头左右）后序（左右头） 二叉树中某个节点X，先序遍历集合中节点X的前面集合为A，后面集合为C，后序遍历集合中节点X的后面集合为B，前面集合为D，证明A与B取交集是X节点的祖先节点？

二叉树分类：X节点，X节点的祖先节点(先序只存在于A集合中，后序只存在于B集合中)， X节点的孩子节点(只存在与C、D集合中)， 以X节点为左树形态下的右兄弟们(先序只存在于C集合中，后序只存在于B集合中)， 以X节点为右树形态下的左兄弟们(先序只存在于A集合中，后序只存在于D集合中)。 综上所述：A与B取交集是X节点的祖先节点

← 第11节 二叉树的基本算法（下） →