Java-07
学习来源：日撸 Java 三百行（21-30天，树与二叉树）_闵帆的博客-CSDN博客
23 使用具有通用性的队列
23.1 Java 里面，所有的类均为 Object 类的 (直接或间接) 子类。如果不写就默认为直接子类。例如
public class CircleObjectQueue;
等价于
public class CircleObjectQueue extends Object;
23.2 存储对象的队列, 实际上是存储对象的地址 (引用、指针)。因此，可以存储任何类的对象（的引用)。
23.3 可以通过强制类型转换将对象转成其本身的类别。例如前面程序
tempTree = (BinaryCharTree) tempQueue.dequeue();
括号中的类型即表示强制类型转换。
23.4Java 本身将 int，double，char 分别封装到 Integer，Double，Char 类。
代码：
package 日撸Java300行_21_30;import java.util.Arrays;import 日撸Java300行_11_20.*;/*** Binary tree with char type elements.* @time 2022/4/4* @author Hui Xiao*/public class BinaryChartTree {/*** The value in char.*/char value;/*** The left child.*/BinaryChartTree leftChild;/*** The right child*/BinaryChartTree rightChild;/******************* The first constructor.* * @param paraName.* The value.*****************/public BinaryChartTree(char paraName) {value = paraName;leftChild = null;rightChild = null;} // Of the constructor/******************* Manually construct a tree. only for testing.*****************/public static BinaryChartTree manualConstructTree() {// Step 1. Construct a tree with only one node.BinaryChartTree resultTree = new BinaryChartTree('a');// Step 2. Construct all nodes. The first node is the root.// BinaryCharTreeNode tempTreeA = resultTree.root;BinaryChartTree tempTreeB = new BinaryChartTree('b');BinaryChartTree tempTreeC = new BinaryChartTree('c');BinaryChartTree tempTreeD = new BinaryChartTree('d');BinaryChartTree tempTreeE = new BinaryChartTree('e');BinaryChartTree tempTreeF = new BinaryChartTree('f');BinaryChartTree tempTreeG = new BinaryChartTree('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 preOderVisit() {System.out.println("" + value + " ");if (leftChild != null) {leftChild.preOderVisit();} // Of ifif (rightChild != null) {rightChild.preOderVisit();} // Of if} // Of preOrderVisit/****************** In-order visit.*************** */public void inOrderVisit() {if (leftChild != null) {leftChild.inOrderVisit();} // Of ifSystem.out.println("" + 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.println("" + 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 geDepth/****************** 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 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 result are stored in tow 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);BinaryChartTree tempTree = (BinaryChartTree) 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 ofif (tempTree.rightChild != null) {tempQueue.enqueue(tempTree.rightChild);tempIntQueue.enqueue(tempIndex * 2 + 2);} // Of iftempTree = (BinaryChartTree) tempQueue.dequeue();tempIndex = tempIntQueue.dequeue();} // Of while} // Of toDataArrayspublic void ToDataArraysObjetcQueue() {//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();Integer tempIndexInteger = Integer.valueOf(0);tempIntQueue.enqueue(tempIndexInteger);BinaryChartTree tempTree = (BinaryChartTree) 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 ofif (tempTree.rightChild != null) {tempQueue.enqueue(tempTree.rightChild);tempIntQueue.enqueue(Integer.valueOf(tempIndex * 2 + 2));} // Of iftempTree = (BinaryChartTree) tempQueue.dequeue();if (tempTree == null) {break;}tempIndex = ((Integer)tempIntQueue.dequeue()).intValue();} // Of while} // Of ToDataArraysObjetcQueue/****************** The entrance of the program.* * @param args Not used now.****************/public static void main(String[] args) {BinaryChartTree tempTree = manualConstructTree();System.out.println("\r\nPreorder visit:");tempTree.preOderVisit();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.ToDataArraysObjetcQueue();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 BinaryCharTree
截图：
24 二叉树的建立
24.1 只增加了一个构造方法。相当于第 22 天的逆过程。
24.2 保留了调拭语句，因为下标很容易出错。
24.3 使用一个线性表先分配所有节点的空间，再将节点链接起来。
24.4 最后并没有返回，而是把第 0 个节点的相应值拷贝给自己。
代码：
package 日撸Java300行_21_30;import java.util.Arrays;import 日撸Java300行_11_20.*;/*** Binary tree with char type elements.* @time 2022/4/4* @author Hui Xiao*/public class BinaryChartTree {/*** The value in char.*/char value;/*** The left child.*/BinaryChartTree leftChild;/*** The right child*/BinaryChartTree rightChild;/******************* The first constructor.* * @param paraName.* The value.*****************/public BinaryChartTree(char paraName) {value = paraName;leftChild = null;rightChild = null;} // Of the constructor/******************* Manually construct a tree. only for testing.*****************/public static BinaryChartTree manualConstructTree() {// Step 1. Construct a tree with only one node.BinaryChartTree resultTree = new BinaryChartTree('a');// Step 2. Construct all nodes. The first node is the root.// BinaryCharTreeNode tempTreeA = resultTree.root;BinaryChartTree tempTreeB = new BinaryChartTree('b');BinaryChartTree tempTreeC = new BinaryChartTree('c');BinaryChartTree tempTreeD = new BinaryChartTree('d');BinaryChartTree tempTreeE = new BinaryChartTree('e');BinaryChartTree tempTreeF = new BinaryChartTree('f');BinaryChartTree tempTreeG = new BinaryChartTree('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 preOderVisit() {System.out.println("" + value + " ");if (leftChild != null) {leftChild.preOderVisit();} // Of ifif (rightChild != null) {rightChild.preOderVisit();} // Of if} // Of preOrderVisit/****************** In-order visit.*************** */public void inOrderVisit() {if (leftChild != null) {leftChild.inOrderVisit();} // Of ifSystem.out.println("" + 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.println("" + 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 geDepth/****************** 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 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 result are stored in tow 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);BinaryChartTree tempTree = (BinaryChartTree) 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 ofif (tempTree.rightChild != null) {tempQueue.enqueue(tempTree.rightChild);tempIntQueue.enqueue(tempIndex * 2 + 2);} // Of iftempTree = (BinaryChartTree) tempQueue.dequeue();tempIndex = tempIntQueue.dequeue();} // Of while} // Of toDataArrayspublic void ToDataArraysObjetcQueue() {//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();Integer tempIndexInteger = Integer.valueOf(0);tempIntQueue.enqueue(tempIndexInteger);BinaryChartTree tempTree = (BinaryChartTree) 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 ofif (tempTree.rightChild != null) {tempQueue.enqueue(tempTree.rightChild);tempIntQueue.enqueue(Integer.valueOf(tempIndex * 2 + 2));} // Of iftempTree = (BinaryChartTree) tempQueue.dequeue();if (tempTree == null) {break;}tempIndex = ((Integer)tempIntQueue.dequeue()).intValue();} // Of while} // Of ToDataArraysObjetcQueue/********************* 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 BinaryChartTree(char[] paraDataArray, int[] paraIndicesArray) {// Step 1. Use a sequental list to store all nodes.int tempNumNodes = paraDataArray.length;BinaryChartTree[] tempAllNodes = new BinaryChartTree[tempNumNodes];for (int i = 0; i < tempNumNodes; i++) {tempAllNodes[i] = new BinaryChartTree(paraDataArray[i]);} // Of for i// Step 2. Link these nodes.for (int i = 0; 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 is} //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 second constructor/****************** The entrance of the program.* * @param args Not used now.****************/public static void main(String[] args) {BinaryChartTree tempTree = manualConstructTree();System.out.println("\r\nPreorder visit:");tempTree.preOderVisit();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.ToDataArraysObjetcQueue();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));char[] tempCharArray = {'A', 'B', 'C', 'D', 'E', 'F'};int[] tempIndicesArray = {0, 1, 2, 4, 5, 12};BinaryChartTree tempTree2 = new BinaryChartTree(tempCharArray, tempIndicesArray);System.out.println("\r\nPreorder visit:");tempTree2.preOderVisit();System.out.println("\r\nIn-order visit:");tempTree2.inOrderVisit();System.out.println("\r\nPost-order visit:");tempTree2.postOrderVisit();} // Of main
} // Of BinaryCharTree
截图：
25-1 具有通用性的对象栈
25-1.1 改写栈程序, 里面存放对象.
25-1.2 该程序应该放在 datastructure.stack 包内.
25-1.3 还是依靠强制类型转换, 支持不同的数据类型.
25-1.4 增加了 isEmpty() 方法.
代码：
package 日撸Java300行_11_20;/*** Circle char queue.* @time 2022/4/9* @author Hui Xiao*/
public class CircleCharQueue {/*** The total space. One space can never be used.*/public static final int TOTAL_SPACE = 10;/*** The data.*/char[] data;/*** The index for calculating the head. The actual head is head % TOTAL_SPACE.*/int head;/*** The index for calculating the tail.*/int tail;/****************** The constructor****************/public CircleCharQueue() {data = new char[TOTAL_SPACE];head = 0;tail = 0;} // Of the first constructor/****************** Enqueue.* * @param paraValue The value of the new node.****************/public void enqueue(char paraValue) {if ((tail + 1) % TOTAL_SPACE == head) {System.out.println("Queue full.");return;} // Of ifdata[tail % TOTAL_SPACE] = paraValue;tail++;} // Of enqueue/****************** Dequeue.* * @return The value at the head.****************/public char dequeue() {if (head == tail) {System.out.println("No element in the queue");return '\0';} // Of ifchar 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 iffor (int i = head; i < tail; i++) {resultString += data[i % TOTAL_SPACE] + ", ";} // Of for ireturn resultString;} // Of toString/****************** The entrance of the program.* * @param args Not used now.****************/public static void main(String[] args) {CircleCharQueue tempQueue = new CircleCharQueue();System.out.println("Initialized, the list is: " + tempQueue.toString());for (char i = '0'; i < '5'; i++) {tempQueue.enqueue(i);} // Of for iSystem.out.println("Enqueue, the queue is: " + tempQueue.toString());char tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + " the queue is: " + tempQueue.toString());for (char i = 'a'; i < 'f'; i++) {tempQueue.enqueue(i);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for ifor (int i = 0; i < 3; i++) {tempValue = tempQueue.dequeue();System.out.println("Dequeue " + tempValue + " the queue is: " + tempQueue.toString());} // Of for ifor (char i = 'A'; i < 'F'; i++) {tempQueue.enqueue(i);System.out.println("Enqueue, the queue is: " + tempQueue.toString());} // Of for i} // Of main
} // Of class CircleCharQueue截图：
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！