日撸Java三百行（day23：使用具有通用性的队列）

前言

一、基础知识准备

1.Object类

2.Integer类

2.1包装类

2.2装箱和拆箱

2.3Integer类的常见方法

二、代码实现

1.队列创建及初始化

2.方法创建

3.数据测试

4.完整的程序代码

总结

前言

在昨天，我们使用了两个队列来辅助完成二叉树的“压缩顺序存储”，一个是存放二叉树结点类型的数据队列，另一个是存放整数类型的下标队列，这样来看，对于不同的数据类型，难道我们都要单独编写一个队列吗？答案显然不是，事实上，我们只需要一个存储对象的队列就可以完成了，今天我们就来学习一下“通用性队列”。

一、基础知识准备

1.Object类

在昨天重写队列代码时，我们只提到了将数据类型char更改为object，并没有对其进行详细的说明，现在我们就来认识一下Object这个“老祖宗”。

其实早在日撸Java三百行（day12：顺序表二）我们第一次重写toString()方法的时候，就已经用到了Object类。在java中，Object类是所有类的根基类（父类），相当于所有类的“老祖宗”，这就意味着所有类都是Object类的子类，都可以继承Object类的属性和方法，也就是说任何java对象都可以调用Object类的方法。

如果在类的声明中，未使用extends关键字指明其父类，那么就会自动默认继承Object类，也就是说以下两种关于类的声明是等价的：

```
public class Person {
...
}
```

public class Person extends Object {
...
}

下面我们再介绍几种Object类常用的方法：

toString()方法：返回该对象的字符串形式
equals()方法：比较两个对象的内容是否相等
getClass()方法：返回该对象所属的类

前面我们说到Object类是所有类的父类，任何java对象都可以调用Object类的方法，由此得出所有类的对象都可以向Object转换，即一切的引用数据类型都可以用Object进行接收。而正是因为Object可以接收任意的引用数据类型，所以很多类都是以Object作为方法的参数，这样操作起来会更加方便。

注意，Object支持null的返回，这个特性关乎我们今日代码的成功与否。

2.Integer类

2.1包装类

java中的数据类型分为两大类，一类是基本数据类型，另一类是引用数据类型。基本数据类型只有8种，包括整数类型（long、int、short、byte），浮点类型（float、double），字符类型（char），布尔类型（boolean）；而引用数据类型包括类、接口类型、数组类型、枚举类型、注解类型、字符串型等，简单来说所有的非基本数据类型都是引用数据类型。

显然，基本数据类型肯定不能够称之为对象，所以java为每种基本数据类型分别设计了对应的类，这个类就是所谓的包装类。包装类是不可修改的，一旦构造了包装类对象，就不能改变对应包装类中的属性和方法，同时包装类是被final关键字修饰的类，因此不能被继承。基本数据类型及对应的包装类如下表：

基本数据类型		对应的包装类
整数类型	byte	Byte
	short	Short
	int	Integer
	long	Long
浮点类型	float	Float
浮点类型	double	Double
字符类型	char	Character
布尔类型	boolean	Boolean

从上表可以看出，除了int和char，其余基本数据类型的包装类名称都只变了首字母。

2.2装箱和拆箱

了解了包装类的概念后，下面我们介绍装箱和拆箱。

装箱：将基本数据类型转换为包装类的过程，比如把int包装成Integer类的对象
拆箱：包装类转换为基本数据类型的过程，比如把Integer类的对象重新简化成int

手动包装一个基本数据类型成对象叫做手动装箱，手动实例化一个包装类叫做手动拆箱。Java 1.5版本之后出现了自动装箱拆箱，即进行基本数据类型和对应包装类的转换时，系统自动进行装箱拆箱操作，不用再自己手动操作。

2.3Integer类的常见方法

longValue()：将Integer类型转换为基本数据类型long
inValue()：将Integer类型转换为基本数据类型int
shortValue()：将Integer类型转换为基本数据类型short
byteValue()：将Integer类型转换为基本数据类型byte
Integer.valueOf(int i)：通过类名直接调用静态方法valueOf()将int转换为Integer类型
Integer.valueOf(String s)：通过类名直接调用静态方法valueOf()将String转换为Integer类型

二、代码实现

1.队列创建及初始化

因为昨天我们重写的队列代码CircleObjectQueue就是Object类型的（即定义的就是存储对象的队列），所以这里直接创建两个对象即可。数据队列将this入队，作为根结点，这个和昨天一样，没什么好说的；接着来到下标队列，由于昨天我们用的是int类型的队列作为下标队列，所以可以直接将索引值0入队，但是今天我们使用了Object类型的队列作为下标队列，而0是int基本数据类型，显然不可能直接入队，需要先利用Integer.valueOf()方法将0转换为Integer类型，然后赋给Integer类型的变量tempIndexInteger，最后再将tempIndexInteger入队。（说明：因为Integer类型是引用数据类型，所以可以被Object接收）

CircleObjectQueue tempQueue = new CircleObjectQueue();
tempQueue.enqueue(this);
CircleObjectQueue tempIntQueue = new CircleObjectQueue();
Integer tempIndexInteger = Integer.valueOf(0);
tempIntQueue.enqueue(tempIndexInteger);

2.方法创建

核心方法的大体思路以及具体步骤几乎和昨天一样，只需要更改几个细节即可。

第2行代码，昨天我们是出队后直接赋给tempIndex，而今天出队后还需要调用intValue()方法，将Integer类型转换为int类型，再赋给int类型的变量tempIndex。为了确保不出错，这里我们增加了一个输出语句，用于检查tempIndex的值是否正确。

第11行代码，和刚刚索引值0入队一样，需要在入队前利用Integer.valueOf()方法将其转换为Integer类型，然后再入队。

第15行代码同上。

第19行代码，在介绍Object类时，我们强调了Object类支持null的返回，该特性影响的就是这个地方。如果在这里我们不增加该if语句，那么就会出现如下的报错，这是因为Object类支持null的返回，但是null无法被int强制转换。为了避免上述问题，我们利用break语句，使得当tempTree = null时就跳出循环。

第23行代码，和第2行代码一样，出队后需要调用intValue()方法将其转换为int类型。

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 ifif (tempTree.leftChild != null) {tempQueue.enqueue(tempTree.leftChild);tempIntQueue.enqueue(Integer.valueOf(tempIndex * 2 + 2));} // of iftempTree = (BinaryCharTree) tempQueue.dequeue();if (tempTree == null) {break;} // of iftempIndex = ((Integer)tempIntQueue.dequeue()).intValue();
} // of while

关于根结点与左右子树下标关系的补充：

这是昨天“压缩顺序存储”的图，我们可以发现

根结点A下标为0，其左子树B下标为1（0*2+1=1），右子树C下标为2（0*2+2=2）；

根结点B下标为1，其无左子树，右子树D下标为4（1*2+2=4）

根结点C下标为2，其左子树E下标为5（2*2+1=5）

…………

所以就有了我们程序中的tempIndex * 2 + 1和tempIndex * 2 + 2。

3.数据测试

然后，仍然借助我们之前手动创建的二叉树进行数据测试，如下：

    /************************ 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

4.完整的程序代码

package datastructure.tree;import datastructure.queue.*;
import java.util.Arrays;
/*** Binary tree with char type elements.**@auther Xin Lin 3101540094@qq.com.*/public class BinaryCharTree {/*** The value*/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 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.// BinaryCharTree 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 ifif(rightChild != null) {rightChild.preOrderVisit();} // of if} // of preOrderVisit/************************ In-order visit.**********************/public void inOrderVisit() {if(leftChild != null) {leftChild.inOrderVisit();} // of ifSystem.out.print("" + value + " ");if(rightChild != null) {rightChild.inOrderVisit();} // of if} // of inOrderVisit/************************ Post-order visit.**********************/public void postOrderVisit() {if(leftChild != null) {leftChild.postOrderVisit();} // of ifif(rightChild != null) {rightChild.postOrderVisit();} // of ifSystem.out.print("" + value + " ");} // of postOrderVisit/************************ Get the depth of the binary char tree.* * @return The depth.**********************/public int getDepth() {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 ifif(tempLeftDepth >= tempRightDepth) {return tempLeftDepth + 1;} else {return tempRightDepth + 1;} // of if} // of getDepth/************************ Get the number of nodes of the binary char tree.* * @return The number of nodes.**********************/public int getNumNodes() {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 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 ifif (tempTree.rightChild != null) {tempQueue.enqueue(tempTree.rightChild);tempIntQueue.enqueue(tempIndex * 2 + 2);} // Of iftempTree = (BinaryCharTree) tempQueue.dequeue();tempIndex = tempIntQueue.dequeue();} // Of while} // Of toDataArrays/*********************** 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 ifif (tempTree.leftChild != null) {tempQueue.enqueue(tempTree.leftChild);tempIntQueue.enqueue(Integer.valueOf(tempIndex * 2 + 2));} // of iftempTree = (BinaryCharTree) tempQueue.dequeue();if (tempTree == null) {break;} // of iftempIndex = ((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	
} // of class BinaryCharTree

运行结果