Java学习-Day11

二叉树的深度遍历的递归实现

一、概述

利用递归遍历二叉树的时候有三种遍历顺序, 分别是先序、中序和后序. 先后顺序是以根节点为基准的. 虽然看起来有三种, 在实际编写代码的时候也只是递归位置的变换.

本文构造的二叉树如下图所示:

二、先序遍历

描述

先访问根节点, 然后递归访问左子树, 最后递归访问右子树.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *********************
 * Pre-order visit.
 *********************
 */
public void preOrderVisit() {
	System.out.print("" + value + " ");

	if (leftChild != null) {
		leftChild.preOrderVisit();
	} // Of if

	if (rightChild != null) {
		rightChild.preOrderVisit();
	} // Of if
}// Of preOrderVisit

三、中序遍历

描述

先递归访问左子树, 然后根节点, 最后递归访问右子树.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *********************
 * In-order visit.
 *********************
 */
public void inOrderVisit() {
	if (leftChild != null) {
		leftChild.inOrderVisit();
	} // Of if

	System.out.print("" + value + " ");

	if (rightChild != null) {
		rightChild.inOrderVisit();
	} // Of if
}// Of inOrderVisit

四、后序遍历

描述

先递归访问左子树, 然后递归访问右子树, 最后根节点.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *********************
 * Post-order visit.
 *********************
 */
public void postOrderVisit() {
	if (leftChild != null) {
		leftChild.postOrderVisit();
	} // Of if

	if (rightChild != null) {
		rightChild.postOrderVisit();
	} // Of if

	System.out.print("" + value + " ");
}// Of postOrderVisit

五、树的深度和节点数

思路

树的深度用递归思想来看就是左右子树深度较大的那部分加上根节点的深度.

那么节点数就更简单了, 只需要在遍历的时候输出一个节点加上一个节点就可以了.

树深度代码

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
/**
	 *********************
	 * Get the depth of the binary tree.
	 * 
	 * @return The depth. It is 1 if there is only one node, i.e., the root.
	 *********************
	 */
	public int getDepth() {
		// It is a leaf.
		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		} // Of if

		// The depth of the left child.
		int tempLeftDepth = 0;
		if (leftChild != null) {
			tempLeftDepth = leftChild.getDepth();
		} // Of if

		// The depth of the right child.
		int tempRightDepth = 0;
		if (rightChild != null) {
			tempRightDepth = rightChild.getDepth();
		} // Of if

		// The depth should increment by 1.
		if (tempLeftDepth >= tempRightDepth) {
			return tempLeftDepth + 1;
		} else {
			return tempRightDepth + 1;
		} // Of if
	}// Of getDepth

树总节点数代码

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
/**
	 *********************
	 * Get the number of nodes.
	 * 
	 * @return The number of nodes.
	 *********************
	 */
	public int getNumNodes() {
		// It is a leaf.
		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		} // Of if

		// The number of nodes of the left child.
		int tempLeftNodes = 0;
		if (leftChild != null) {
			tempLeftNodes = leftChild.getNumNodes();
		} // Of if

		// The number of nodes of the right child.
		int tempRightNodes = 0;
		if (rightChild != null) {
			tempRightNodes = rightChild.getNumNodes();
		} // Of if

		// The total number of nodes.
		return tempLeftNodes + tempRightNodes + 1;
	}// Of getNumNodes

六、完整代码

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
package datastructure.tree;

/**
 * Binary tree with char type elements.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class BinaryCharTree {
	/**
	 * The value in char.
	 */
	char value;

	/**
	 * The left child.
	 */
	BinaryCharTree leftChild;

	/**
	 * The right child.
	 */
	BinaryCharTree rightChild;

	/**
	 *********************
	 * The first constructor.
	 * 
	 * @param paraName The value.
	 *********************
	 */
	public BinaryCharTree(char paraName) {
		value = paraName;
		leftChild = null;
		rightChild = null;
	}// Of the constructor

	/**
	 *********************
	 * Manually construct a tree. Only for testing.
	 *********************
	 */
	public static BinaryCharTree manualConstructTree() {
		// Step 1. Construct a tree with only one node.
		BinaryCharTree resultTree = new BinaryCharTree('a');

		// Step 2. Construct all nodes. The first node is the root.
		// BinaryCharTreeNode tempTreeA = resultTree.root;
		BinaryCharTree tempTreeB = new BinaryCharTree('b');
		BinaryCharTree tempTreeC = new BinaryCharTree('c');
		BinaryCharTree tempTreeD = new BinaryCharTree('d');
		BinaryCharTree tempTreeE = new BinaryCharTree('e');
		BinaryCharTree tempTreeF = new BinaryCharTree('f');
		BinaryCharTree tempTreeG = new BinaryCharTree('g');

		// Step 3. Link all nodes.
		resultTree.leftChild = tempTreeB;
		resultTree.rightChild = tempTreeC;
		tempTreeB.rightChild = tempTreeD;
		tempTreeC.leftChild = tempTreeE;
		tempTreeD.leftChild = tempTreeF;
		tempTreeD.rightChild = tempTreeG;

		return resultTree;
	}// Of manualConstructTree

	/**
	 *********************
	 * Pre-order visit.
	 *********************
	 */
	public void preOrderVisit() {
		System.out.print("" + value + " ");

		if (leftChild != null) {
			leftChild.preOrderVisit();
		} // Of if

		if (rightChild != null) {
			rightChild.preOrderVisit();
		} // Of if
	}// Of preOrderVisit

	/**
	 *********************
	 * In-order visit.
	 *********************
	 */
	public void inOrderVisit() {
		if (leftChild != null) {
			leftChild.inOrderVisit();
		} // Of if

		System.out.print("" + value + " ");

		if (rightChild != null) {
			rightChild.inOrderVisit();
		} // Of if
	}// Of inOrderVisit

	/**
	 *********************
	 * Post-order visit.
	 *********************
	 */
	public void postOrderVisit() {
		if (leftChild != null) {
			leftChild.postOrderVisit();
		} // Of if

		if (rightChild != null) {
			rightChild.postOrderVisit();
		} // Of if

		System.out.print("" + value + " ");
	}// Of postOrderVisit

	/**
	 *********************
	 * Get the depth of the binary tree.
	 * 
	 * @return The depth. It is 1 if there is only one node, i.e., the root.
	 *********************
	 */
	public int getDepth() {
		// It is a leaf.
		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		} // Of if

		// The depth of the left child.
		int tempLeftDepth = 0;
		if (leftChild != null) {
			tempLeftDepth = leftChild.getDepth();
		} // Of if

		// The depth of the right child.
		int tempRightDepth = 0;
		if (rightChild != null) {
			tempRightDepth = rightChild.getDepth();
		} // Of if

		// The depth should increment by 1.
		if (tempLeftDepth >= tempRightDepth) {
			return tempLeftDepth + 1;
		} else {
			return tempRightDepth + 1;
		} // Of if
	}// Of getDepth

	/**
	 *********************
	 * Get the number of nodes.
	 * 
	 * @return The number of nodes.
	 *********************
	 */
	public int getNumNodes() {
		// It is a leaf.
		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		} // Of if

		// The number of nodes of the left child.
		int tempLeftNodes = 0;
		if (leftChild != null) {
			tempLeftNodes = leftChild.getNumNodes();
		} // Of if

		// The number of nodes of the right child.
		int tempRightNodes = 0;
		if (rightChild != null) {
			tempRightNodes = rightChild.getNumNodes();
		} // Of if

		// The total number of nodes.
		return tempLeftNodes + tempRightNodes + 1;
	}// Of getNumNodes

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		BinaryCharTree tempTree = manualConstructTree();
		System.out.println("\r\nPreorder visit:");
		tempTree.preOrderVisit();
		System.out.println("\r\nIn-order visit:");
		tempTree.inOrderVisit();
		System.out.println("\r\nPost-order visit:");
		tempTree.postOrderVisit();

		System.out.println("\r\n\r\nThe depth is: " + tempTree.getDepth());
		System.out.println("The number of nodes is: " + tempTree.getNumNodes());
	}// Of main
} // Of class BinaryCharTree

七、运行截图

二叉树的存储

一、描述

二叉树的存储并非一个简单的问题. 引用 (指针) 是无法存储到文件里面的.

当然要是不考虑复杂性的话, 我首选就是拿 XML 或者 JSON 的文件格式来存储, 这不仅可以解决二叉树的存储问题, 还能在一个文件里面实现多个二叉树的存储.但是如果二叉树的深度过高就会出现看起来很奇怪的文件格式.

我们可以完全满二叉树的角度广度优先遍历的角度来考虑这个问题: 每个节点都有一个 name 及其在二叉树中的位置. 令根节点的位置为 0; 则第 2 层节点的位置依次为 1 至 2; 第 3 层节点的位置依次为 3 至 6. 以此类推.

  1. 空使用 0 来表示, 可以用一个向量来存储: [a, b, c, 0, d, e, 0, 0, 0, f, g] 优点: 仅需要一个向量, 简单直接. 缺点: 对于实际的二叉树, 很多子树为空, 导致大量的 0 值.

  2. 使用压缩存储方式, 即将节点的位置和值均存储. 可表示为两个向量: [0, 1, 2, 4, 5, 9, 10] [a, b, c, d, e, f, g]

为什么不在每个存在的节点后就直接存储它的位置呢？ 可能分类看起来要好看得多.

二、层序遍历

因为从思考的方式来看就需要每层每层访问二叉树, 这里就需要用到之前所学过的队列.

那么编写适合二叉树的队列, 具体代码如下. 

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
package datastructure.queue;

/**
 * Circle Object queue.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class CircleObjectQueue {
	/**
	 * The total space. One space can never be used.
	 */
	public static final int TOTAL_SPACE = 10;

	/**
	 * The data.
	 */
	Object[] data;

	/**
	 * The index of the head.
	 */
	int head;

	/**
	 * The index of the tail.
	 */
	int tail;

	/**
	 ******************* 
	 * The constructor
	 ******************* 
	 */
	public CircleObjectQueue() {
		data = new Object[TOTAL_SPACE];
		head = 0;
		tail = 0;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(Object paraValue) {
		if ((tail + 1) % TOTAL_SPACE == head) {
			System.out.println("Queue full.");
			return;
		} // Of if

		data[tail % TOTAL_SPACE] = paraValue;
		tail++;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the head.
	 *********************
	 */
	public Object dequeue() {
		if (head == tail) {
			// System.out.println("No element in the queue");
			return null;
		} // Of if

		Object resultValue = data[head % TOTAL_SPACE];

		head++;

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (head == tail) {
			return "empty";
		} // Of if

		for (int i = head; i < tail; i++) {
			resultString += data[i % TOTAL_SPACE] + ", ";
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CircleObjectQueue tempQueue = new CircleObjectQueue();
	}// Of main

} // Of class CircleObjectQueue

三、存储实现

关键公式

需要注意的是

节点左儿子编号为: \[ leftNum = fatherNum \times 2 + 1 \]

节点右儿子编号为: \[ rightNum = fatherNum \times 2 + 2 \]

具体代码

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
/**
 * The values of nodes according to breadth first traversal.
 */
char[] valuesArray;

/**
 * The indices in the complete binary tree.
 */
int[] indicesArray;

/**
 ********************
 * Convert the tree to data arrays, including a char array and an int array.
 * The results are stored in two member variables.
 * 
 * @see #valuesArray
 * @see #indicesArray
 *********************
 */
public void toDataArrays() {
	//Initialize arrays.
	int tempLength = getNumNodes();

	valuesArray = new char[tempLength];
	indicesArray = new int[tempLength];
	int i = 0;

	//Traverse and convert at the same time.
	CircleObjectQueue tempQueue = new CircleObjectQueue();
	tempQueue.enqueue(this);
	CircleIntQueue tempIntQueue = new CircleIntQueue();
	tempIntQueue.enqueue(0);

	BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
	int tempIndex = tempIntQueue.dequeue();
	while (tempTree != null) {
		valuesArray[i] = tempTree.value;
		indicesArray[i] = tempIndex;
		i++;

		if (tempTree.leftChild != null) {
			tempQueue.enqueue(tempTree.leftChild);
			tempIntQueue.enqueue(tempIndex * 2 + 1);
		} // Of if

		if (tempTree.rightChild != null) {
			tempQueue.enqueue(tempTree.rightChild);
			tempIntQueue.enqueue(tempIndex * 2 + 2);
		} // Of if

		tempTree = (BinaryCharTree) tempQueue.dequeue();
		tempIndex = tempIntQueue.dequeue();
	} // Of while
}// Of toDataArrays

运行截图

总结

二叉树说实话, 至少在我遇到的项目中还很难使用到. 大部分也只是对数据的处理, 对界面的设计. 在刷算法里面经常遇见, 大概率是我层级太低.

一定一定要注意的是对树的判空.