Java学习-Day12

使用具有通用性的队列

一、描述

之前使用的队列有两种: 存储二叉树节点的队列; 存储整数的队列. 这样的话, 难道我们要为每种类型单独写一个队列? 这样显然没有充分利用代码的复用性. 实际上, 我们只需要一个存储对象的队列就够啦!

这个问题在之前总结的时候就已经提到了.

  1. Java 里面, 所有的类均为 Object 类的 (直接或间接) 子类. 如果不写就默认为直接子类. 例如

    public class CircleObjectQueue;

    等价于

    public class CircleObjectQueue extends Object;

  2. 存储对象的队列, 实际上是存储对象的地址 (引用、指针). 因此, 可以存储任何类的对象 (的引用).

  3. 可以通过强制类型转换将对象转成其本身的类别. 例如前面程序

    tempTree = (BinaryCharTree) tempQueue.dequeue();

    括号中的类型即表示强制类型转换.

  4. Java 本身将 int, double, char 分别封装到 Integer, Double, Char 类. 封装起来叫装包, 解析使用的时候叫拆包.

二、具体代码

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
/**
 ********************
 * 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 toDataArraysObjectQueue() {
	// 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);
	CircleObjectQueue tempIntQueue = new CircleObjectQueue();
	Integer tempIndexInteger = Integer.valueOf(0);
	tempIntQueue.enqueue(tempIndexInteger);

	BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
	int tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
	System.out.println("tempIndex = " + tempIndex);
	while (tempTree != null) {
		valuesArray[i] = tempTree.value;
		indicesArray[i] = tempIndex;
		i++;

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

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

		tempTree = (BinaryCharTree) tempQueue.dequeue();
		if (tempTree == null) {
			break;
		} // Of if

		tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
	} // Of while
}// Of toDataArraysObjectQueue

/**
 *********************
 * 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());

	tempTree.toDataArrays();
	System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
	System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));

	tempTree.toDataArraysObjectQueue();
	System.out.println("Only object queue.");
	System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
	System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));

}// Of main

三、运行截图

二叉树的建立

一、描述

在之前我们获得了如何将二叉树存储起来的方法和代码, 那么现在我们要做的工作就是把存储起来的数据还原为一颗完整的二叉树. 简而言之就是二叉树存储的逆过程.

二、思考

因为根据二叉树的属性这里还是使用下标的特殊性. 总体上来说先构建根节点, 然后按照每一层有一个最大序号构建当前层.

也可以脑中构建一个树, 然后想象把他们连接在一起.

三、具体实现

过程

第一步将所有节点的值存储到一个数组中.

第二步是以子节点为基准来找它们的父节点.

第三步就是把得到的根节点赋值给当前二叉树.

为什么可以这么做呢？

因为父节点始终是在子节点前。那么循环外层是以子节点为基准就应该从 1 开始, 因为 0 是毋庸置疑的根节点, 循环内部就是在子节点之前所有的节点, 而对于满足公式的节点就是该节点的父节点, 同时也可以知道是左节点还是右节点.

具体代码

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
/**
 *********************
 * The second constructor. The parameters must be correct since no validity
 * check is undertaken.
 * 
 * @param paraDataArray    The array for data.
 * @param paraIndicesArray The array for indices.
 *********************
 */
public BinaryCharTree(char[] paraDataArray, int[] paraIndicesArray) {
	// Step 1. Use a sequential list to store all nodes.
	int tempNumNodes = paraDataArray.length;
	BinaryCharTree[] tempAllNodes = new BinaryCharTree[tempNumNodes];
	for (int i = 0; i < tempNumNodes; i++) {
		tempAllNodes[i] = new BinaryCharTree(paraDataArray[i]);
	} // Of for i

	// Step 2. Link these nodes.
	for (int i = 1; i < tempNumNodes; i++) {
		for (int j = 0; j < i; j++) {
			System.out.println("indices " + paraIndicesArray[j] + " vs. " + paraIndicesArray[i]);
			if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 1) {
				tempAllNodes[j].leftChild = tempAllNodes[i];
				System.out.println("Linking " + j + " with " + i);
				break;
			} else if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 2) {
				tempAllNodes[j].rightChild = tempAllNodes[i];
				System.out.println("Linking " + j + " with " + i);
				break;
			} // Of if
		} // Of for j
	} // Of for i

	// Step 3. The root is the first node.
	value = tempAllNodes[0].value;
	leftChild = tempAllNodes[0].leftChild;
	rightChild = tempAllNodes[0].rightChild;
}// Of the the second constructor

运行截图

总结

很多代码关键的就那么一个步骤, 不仅仅是这个还原二叉树和存储二叉树的公式, 还有更多例如动态规划转移方程. 所以说编程的核心还是和数学有着很大关系.

代数和离散甚至于更多我没有接触过的领域都会在我未来的生活中指引我前进.