闵老板の帖子: 日撸 Java 三百行（21-30天，树与二叉树）
2021年秋季第六周周报内容
1. 二叉树的深度遍历的递归实现
树是数据结构中的重中之重, 特别是二叉树.许多实际问题抽象出来的数据结构往往是二叉树形式, 即使是一般的树也能简单地转换为二叉树, 而且二叉树的存储结构及其算法都较为简单, 因此二叉树显得特别重要. 二叉树特点是每个结点最多只能有两棵子树, 且有左右之分.
这里用递归的方法为二叉树写了几个方法:
1. 遍历. 包括前序, 中序, 后序遍历.
2. 计算深度的方法.
3. 计算总结点数的方法.
package datastructure.tree;
public class BinaryTree {
// The value;
char value;
// The left child;
BinaryTree leftChild;
// The right child;
BinaryTree rightChild;
public BinaryTree(char paraValue) {
value = paraValue;
leftChild = null;
rightChild = null;
}// Of one constructor
public static BinaryTree manualConstructTree() {
// The root of the tree.
BinaryTree resultTree = new BinaryTree('A');
// The other nodes.
BinaryTree tempTreeB = new BinaryTree('B');
BinaryTree tempTreeC = new BinaryTree('C');
BinaryTree tempTreeD = new BinaryTree('D');
BinaryTree tempTreeE = new BinaryTree('E');
BinaryTree tempTreeF = new BinaryTree('F');
BinaryTree tempTreeG = new BinaryTree('G');
// link them.
resultTree.leftChild = tempTreeB;
resultTree.rightChild = tempTreeC;
tempTreeB.rightChild = tempTreeD;
tempTreeC.leftChild = tempTreeE;
tempTreeD.leftChild = tempTreeF;
tempTreeD.rightChild = tempTreeG;
return resultTree;
}// Of manualConstrucTree
public void preOrder() {
System.out.print(value + " ");
if(leftChild != null) {
leftChild.preOrder();
}// Of if
if(rightChild != null) {
rightChild.preOrder();
}// Of if
}// Of preOrder
public void inOrder() {
if(leftChild != null) {
leftChild.inOrder();
}// Of if
System.out.print(value + " ");
if(rightChild != null) {
rightChild.inOrder();
}// Of if
}// Of inOrder.
public void postOrder() {
if(leftChild != null) {
leftChild.postOrder();
}// Of if
if(rightChild != null) {
rightChild.postOrder();
}// Of if
System.out.print(value + " ");
}// Of postOrder.
public int getDepth() {
if(leftChild == null && rightChild == null) {
return 1;
}// Of if
int tempLeftDepth = 0, tempRightDepth = 0;
if(leftChild != null) {
tempLeftDepth = leftChild.getDepth();
}// Of if
if(rightChild != null) {
tempRightDepth = rightChild.getDepth();
}// Of if
if(tempLeftDepth >= tempRightDepth) {
return tempLeftDepth+1;
}// Of if
else{
return tempRightDepth+1;
}// Of else
}// Of getDepth
public int getNumNodes() {
if ((leftChild == null) && (rightChild == null)) {
return 1;
} // Of if
int tempLeftNodes = 0, tempRightNodes = 0;
if (leftChild != null) {
tempLeftNodes = leftChild.getNumNodes();
} // Of if
if (rightChild != null) {
tempRightNodes = rightChild.getNumNodes();
} // Of if
return tempLeftNodes + tempRightNodes + 1;
}// Of getNumNodes.
public static void main(String args[]) {
BinaryTree tempTree = manualConstructTree();
System.out.println("Pre-order visit:");
tempTree.preOrder();
System.out.println("rIn-order visit:");
tempTree.inOrder();
System.out.println("rPost-order visit:");
tempTree.postOrder();
System.out.println("rThe depth is: " + tempTree.getDepth());
System.out.println("The number of nodes is: " + tempTree.getNumNodes());
}// Of main
}// Of BinaryCharTree
输出:
Pre-order visit: A B D F G C E In-order visit: B F D G A E C Post-order visit: F G D B E C A The depth is: 4 The number of nodes is: 72. 二叉树的存储
我们可以完全满二叉树的角度广度优先遍历的角度来考虑这个问题: 每个节点都有一个 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]
我们用队列的方式来定义. 与之前不同的是, 这次定义用的是Object类型, 它可以接收任意类型的数据.
package datastructure;
public class CircularObjectQueue {
// The total space. But the actual sapce will be one less.
public static final int MAX_SIZE = 10;
// The data;
Object[] data;
// The index of the head.
int front;
// The index of the tail.
int rear;
public CircularObjectQueue() {
data = new Object[MAX_SIZE];
front = 0;
rear = 0;
}// Of the constructor
public boolean enqueue(Object paraValue) {
if(front == (rear + 1) % MAX_SIZE) {
// System.out.println("Queue full");
return false;
}
data[rear % MAX_SIZE] = paraValue;
rear++;
return true;
}// Of enqueue
public Object dequeue() {
Object resultValue;
if(front == rear) {
// System.out.println("The queue is empty, dequeue fail");
return null;
}// Of if
resultValue = data[front % MAX_SIZE];
front++;
return resultValue;
}// Of dequeue
public String toString() {
String resultString = "";
if(front == rear) {
return "empty";
}// Of if
for(int i = front; i < rear - 1; i++) {
resultString += data[i % MAX_SIZE] + ", ";
}// Of for i
resultString += data[(rear-1) % MAX_SIZE];
return resultString;
}// Of toString
}// Of class CircularObjectQueue
下面是老师的代码实现. 将内容位置应在之前写的BinaryTree.java中.
需要注意的是,节点的索引从0开始. 那么节点的左孩子的索引是其索引的二倍+1, 右孩子是其索引的二倍+2.
char[] valuesArray;
int[] 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
public static void main(String args[]) {
BinaryCharTree tempTree = manualConstructTree();
System.out.println("rnPreorder visit:");
tempTree.preOrderVisit();
System.out.println("rnIn-order visit:");
tempTree.inOrderVisit();
System.out.println("rnPost-order visit:");
tempTree.postOrderVisit();
System.out.println("rnrnThe 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));
}// Of main
输出:
Preorder visit: A B D F G C E In-order visit: B F D G A E C Post-order visit: F G D B E C A The depth is: 4 The number of nodes is: 7 The values are: [A, B, C, D, E, F, G] The indices are: [0, 1, 2, 4, 5, 9, 10]3. 使用具有通用性的队列
我们刚刚已经知道, Object可以用来接收任意类型数据, 那么我们在定义队列的时候, 也不再需要专门去为不同的数据类型创建不同的队列了.
我们可以直接这样定义数据:
Object[] data;
但是在使用的时候, 需要利用强制类型转换使其变成本身的类别. 比如
tempTree = (BinaryCharTree) tempQueue.dequeue();
4. 二叉树的建立这里是二叉树的另一种构造方法, 通过输入相应的valuesArray、indicesArray来构造.
主要有三个步骤:
1. 创建一个Binary类型的数组来存储我们需要的所有节点.
2. 采用双重循环的方式判断是否为某个节点的左右孩子. 这里设计的十分巧妙, 从除根节点外的第一个节点出发, 判断其与之前的节点是否满足为其左右孩子的条件, 若满足条件, 则用之前创建好的Binary类型节点链接起来, 然后跳出循环, 判断下一个节点, 以此直到所有节点判断完毕.
3. 链接完毕, 回到根节点.
public BinaryTree(char[] paraValuesArray, int[] paraIndicesArray) {
// Step 1. Use a sequential list to store all nodes.
int tempNumNodes = paraValuesArray.length;
BinaryTree[] tempAllNodes = new BinaryTree[tempNumNodes];
for (int i = 0; i < tempNumNodes; i++) {
tempAllNodes[i] = new BinaryTree(paraValuesArray[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 third constructor
5. 二叉树深度遍历的栈实现 (中序)
5.1 构建通用栈
在之前写的stack.java中稍作修改, 并添加了.isEmpty()方法.
package datastructure.Stack;
public class ObjectStack {
// The max depth of the stack.
public static final int MAX_DEPTH = 10;
// The actual depth of the stack.
int depth;
// The data.
Object[] data;
public ObjectStack() {
depth = 0;
data = new Object[MAX_DEPTH];
}// Of the constructor
public boolean push(Object paraObject) {
if (depth == MAX_DEPTH) {
System.out.println("The stack is full, push fail");
return false;
} // Of if
data[depth] = paraObject;
depth++;
return true;
}// Of push
public Object pop() {
if (depth == 0) {
System.out.println("The stack is empty, pop fail");
return ' ';
} // Of if
Object resultValue = data[depth - 1];
depth--;
return resultValue;
}// Of pop
public String toString() {
String resultString = "";
if (depth == 0) {
return "empty";
} // Of if
for (int i = 0; i < depth; i++) {
resultString += data[i];
} // Of for i
return resultString;
}// Of toString
public boolean isEmpty() {
if(depth == 0) {
return true;
}// Of if
return false;
}// Of isEmpty
}// Of class ObjectStack
5.2 中序遍历
简单来说, 入左, 左空出左,入右...
public void inOrderWithStack() {
ObjectStack tempStack = new ObjectStack();
BinaryTree tempNode = this;
while (! tempStack.isEmpty() || tempNode != null) {
if (tempNode != null) {
tempStack.push(tempNode);
tempNode = tempNode.leftChild;
} else {
tempNode = (BinaryTree) tempStack.pop();
System.out.print(tempNode.value + " ");
tempNode = tempNode.rightChild;
} // Of if
} // Of while
}// Of inOrderVisit
6. 小结
看不懂就反复看, 或者画图画出来, 多敲几遍, 然后自己琢磨.
