Skip to content

Commit 2379031

Browse files
thlclythlcly
committed
1. 完成数据结构习题
2. 完成测试用例 3. 二叉树添加delete()， search()， min()， max() 方法
1 parent f21458d commit 2379031

29 files changed

+1834
-0
lines changed

‎group01/954958168/954958168.md

Whitespace-only changes.

‎group01/954958168/class01/BasicDataStructure/.gitignore

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# Created by .ignore support plugin (hsz.mobi)
2+
### Java template
3+
*.class
4+
5+
# Log file
6+
*.log
7+
8+
# BlueJ files
9+
*.ctxt
10+
11+
# Mobile Tools for Java (J2ME)
12+
.mtj.tmp/
13+
14+
# Package Files #
15+
*.jar
16+
*.war
17+
*.ear
18+
*.zip
19+
*.tar.gz
20+
*.rar
21+
22+
# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
23+
hs_err_pid*
24+
25+
# Idea Files #
26+
.idea
27+
*.iml
28+

‎group01/954958168/class01/BasicDataStructure/pom.xml

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
3+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
4+
<modelVersion>4.0.0</modelVersion>
5+
6+
<groupId>com.aaront.execrise</groupId>
7+
<artifactId>coding2017</artifactId>
8+
<version>1.0.0-SNAPSHOT</version>
9+
<packaging>jar</packaging>
10+
11+
12+
<properties>
13+
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
14+
<java.version>1.8</java.version>
15+
</properties>
16+
17+
<dependencies>
18+
<dependency>
19+
<groupId>junit</groupId>
20+
<artifactId>junit</artifactId>
21+
<version>4.12</version>
22+
</dependency>
23+
</dependencies>
24+
</project>

‎group01/954958168/class01/BasicDataStructure/src/main/java/com/aaront/exercise/basic/ArrayList.java

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
package com.aaront.exercise.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private static final double factor = 0.75;
10+
11+
private Object[] elementData = new Object[100];
12+
13+
public void add(Object o) {
14+
_ensureCapacityEnough();
15+
elementData[size++] = o;
16+
}
17+
18+
public void add(int index, Object o) {
19+
if (index < 0 || index > size) throw new IndexOutOfBoundsException("index超出边界");
20+
_ensureCapacityEnough();
21+
int i = size;
22+
for (; i > index; i--) {
23+
elementData[i] = elementData[i - 1];
24+
}
25+
elementData[i] = o;
26+
size++;
27+
}
28+
29+
private void _ensureCapacityEnough() {
30+
if (size >= elementData.length) {
31+
dilatancy();
32+
}
33+
}
34+
35+
private void dilatancy() {
36+
int newLength = elementData.length + (int) (elementData.length * factor);
37+
elementData = Arrays.copyOf(elementData, newLength);
38+
}
39+
40+
public Object get(int index) {
41+
if(index < 0 || index >= size) throw new IndexOutOfBoundsException("index超出边界");
42+
return elementData[index];
43+
}
44+
45+
public Object remove(int index) {
46+
if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index超出边界");
47+
Object element = elementData[index];
48+
System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);
49+
size--;
50+
return element;
51+
52+
}
53+
54+
public int size() {
55+
return size;
56+
}
57+
58+
public Iterator iterator() {
59+
return new ArrayListIterator(this);
60+
}
61+
62+
public Object[] toArray() {
63+
Object[] objects = new Object[size];
64+
System.arraycopy(elementData, 0, objects, 0, size);
65+
return objects;
66+
}
67+
68+
private static class ArrayListIterator implements Iterator {
69+
70+
private ArrayList arrayList;
71+
private int pos = 0;
72+
73+
private ArrayListIterator(ArrayList arrayList) {
74+
this.arrayList = arrayList;
75+
}
76+
77+
public boolean hasNext() {
78+
return pos < arrayList.size();
79+
}
80+
81+
public Object next() {
82+
return arrayList.elementData[pos++];
83+
}
84+
85+
public void remove() {
86+
arrayList.remove(pos - 1);
87+
pos--;
88+
}
89+
}
90+
}

‎group01/954958168/class01/BasicDataStructure/src/main/java/com/aaront/exercise/basic/BinaryTree.java

Lines changed: 235 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,235 @@
1+
package com.aaront.exercise.basic;
2+
3+
public class BinaryTree {
4+
5+
private BinaryTreeNode head = new BinaryTreeNode(null);
6+
private BinaryTreeNode root;
7+
private int size;
8+
private int index = 0;
9+
10+
public static final int PREORDER = 0;
11+
public static final int INORDER = 1;
12+
public static final int POSTORDER = 2;
13+
public static final int HIERARCHICAL = 3;
14+
15+
public static final int RECURSION = 10;
16+
public static final int ITERATION = 11;
17+
18+
public void add(Integer o) {
19+
BinaryTreeNode node = new BinaryTreeNode(o);
20+
if (root == null) {
21+
root = node;
22+
head.setLeft(root);
23+
} else {
24+
insert(root, node);
25+
}
26+
size++;
27+
}
28+
29+
private void insert(BinaryTreeNode node, BinaryTreeNode newNode) {
30+
// 要插入的节点插入当前节点的左子树
31+
if (node.getData() > newNode.getData()) {
32+
if (node.getLeft() == null) {
33+
node.setLeft(newNode);
34+
} else {
35+
insert(node.left, newNode);
36+
}
37+
} else { // 要插入的节点插入当前节点的右子树
38+
if (node.getRight() == null) {
39+
node.setRight(newNode);
40+
} else {
41+
insert(node.right, newNode);
42+
}
43+
}
44+
}
45+
46+
public BinaryTreeNode search(int data) {
47+
return search(data, ITERATION);
48+
}
49+
50+
public BinaryTreeNode search(int data, int method) {
51+
switch (method) {
52+
case RECURSION:
53+
return findNodeRecursion(root, data);
54+
case ITERATION:
55+
return findNodeIteration(data);
56+
default:
57+
throw new IllegalArgumentException("不支持的查找方法");
58+
}
59+
}
60+
61+
private BinaryTreeNode findNodeRecursion(BinaryTreeNode node, int data) {
62+
if (node == null) return null;
63+
if (node.getData() == data) return node;
64+
if (node.getData() > data) return findNodeRecursion(node.getLeft(), data);
65+
return findNodeRecursion(node.getRight(), data);
66+
}
67+
68+
private BinaryTreeNode findNodeIteration(int data) {
69+
BinaryTreeNode currentNode = root;
70+
while (currentNode != null) {
71+
if (currentNode.getData() == data) {
72+
return currentNode;
73+
}
74+
if (currentNode.getData() > data) {
75+
currentNode = currentNode.getLeft();
76+
} else {
77+
currentNode = currentNode.getRight();
78+
}
79+
}
80+
return null;
81+
}
82+
83+
public BinaryTreeNode min() {
84+
return findMin(root);
85+
}
86+
87+
private BinaryTreeNode findMin(BinaryTreeNode node) {
88+
if (node == null) return null;
89+
if (node.getLeft() == null) return node;
90+
return findMin(node.getLeft());
91+
}
92+
93+
public BinaryTreeNode max() {
94+
return findMax(root);
95+
}
96+
97+
private BinaryTreeNode findMax(BinaryTreeNode node) {
98+
if (node == null) return null;
99+
if (node.getRight() == null) return node;
100+
return findMax(node.getRight());
101+
}
102+
103+
public void delete(Integer data) {
104+
BinaryTreeNode node = search(data);
105+
if (node == null) return;
106+
BinaryTreeNode parentNode = searchParentNode(node);
107+
if (parentNode == null) return;
108+
// 删除叶子节点
109+
if (node.getLeft() == null && node.getRight() == null) {
110+
if (parentNode.getLeft() == node) parentNode.setLeft(null);
111+
else parentNode.setRight(null);
112+
} else if (node.getLeft() != null && node.getRight() == null) { // 删除只有左子树的节点
113+
if (parentNode.getLeft() == node) parentNode.setLeft(node.getLeft());
114+
else parentNode.setRight(node.getLeft());
115+
} else if (node.getRight() != null && node.getLeft() == null) { // 删除只有右子树的节点
116+
if (parentNode.getLeft() == node) parentNode.setLeft(node.getRight());
117+
else parentNode.setRight(node.getRight());
118+
} else { // 删除有两个子树的节点
119+
BinaryTreeNode replace = findMin(node.getRight());
120+
BinaryTreeNode replaceParentNode = searchParentNode(replace);
121+
replaceParentNode.setLeft(replace.getRight());
122+
node.setData(replace.getData());
123+
replace.setLeft(null);
124+
replace.setRight(null);
125+
}
126+
size--;
127+
}
128+
129+
private BinaryTreeNode searchParentNode(BinaryTreeNode node) {
130+
if (node == null) return null;
131+
if (node == root) return head;
132+
BinaryTreeNode current = root;
133+
while (current != null) {
134+
if (current.getLeft() == node || current.getRight() == node) return current;
135+
if (current.getData().compareTo(node.getData()) > 0) current = current.getLeft();
136+
else current = current.getRight();
137+
}
138+
return null;
139+
}
140+
141+
public int[] traversal() {
142+
return traversal(PREORDER);
143+
}
144+
145+
public int[] traversal(int order) {
146+
int[] datas = new int[size];
147+
if (order == PREORDER) {
148+
preorderTraversal(root, datas);
149+
} else if (order == INORDER) {
150+
inorderTraversal(root, datas);
151+
} else if (order == POSTORDER) {
152+
postorderTraversal(root, datas);
153+
} else {
154+
hierarchicalTraversal(root, datas);
155+
}
156+
index = 0;
157+
return datas;
158+
}
159+
160+
private void preorderTraversal(BinaryTreeNode node, int[] datas) {
161+
if (node == null) {
162+
return;
163+
}
164+
165+
datas[index++] = node.getData();
166+
preorderTraversal(node.getLeft(), datas);
167+
preorderTraversal(node.getRight(), datas);
168+
}
169+
170+
private void inorderTraversal(BinaryTreeNode node, int[] datas) {
171+
if (node == null) {
172+
return;
173+
}
174+
175+
inorderTraversal(node.getLeft(), datas);
176+
datas[index++] = node.getData();
177+
inorderTraversal(node.getRight(), datas);
178+
}
179+
180+
private void postorderTraversal(BinaryTreeNode node, int[] datas) {
181+
if (node == null) {
182+
return;
183+
}
184+
185+
postorderTraversal(node.getLeft(), datas);
186+
postorderTraversal(node.getRight(), datas);
187+
datas[index++] = node.getData();
188+
}
189+
190+
private void hierarchicalTraversal(BinaryTreeNode node, int[] datas) {
191+
if (node == null) return;
192+
Queue queue = new Queue();
193+
queue.enQueue(node);
194+
while (!queue.isEmpty()) {
195+
BinaryTreeNode tmp = (BinaryTreeNode) queue.deQueue();
196+
datas[index++] = tmp.getData();
197+
if (tmp.getLeft() != null) queue.enQueue(tmp.getLeft());
198+
if (tmp.getRight() != null) queue.enQueue(tmp.getRight());
199+
}
200+
}
201+
202+
public class BinaryTreeNode {
203+
private Integer data;
204+
private BinaryTreeNode left;
205+
private BinaryTreeNode right;
206+
207+
public BinaryTreeNode(Integer data) {
208+
this.data = data;
209+
}
210+
211+
public Integer getData() {
212+
return data;
213+
}
214+
215+
public void setData(Integer data) {
216+
this.data = data;
217+
}
218+
219+
public BinaryTreeNode getLeft() {
220+
return left;
221+
}
222+
223+
public void setLeft(BinaryTreeNode left) {
224+
this.left = left;
225+
}
226+
227+
public BinaryTreeNode getRight() {
228+
return right;
229+
}
230+
231+
public void setRight(BinaryTreeNode right) {
232+
this.right = right;
233+
}
234+
}
235+
}

‎group01/954958168/class01/BasicDataStructure/src/main/java/com/aaront/exercise/basic/Iterator.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.aaront.exercise.basic;
2+
3+
public interface Iterator {
4+
boolean hasNext();
5+
6+
Object next();
7+
8+
void remove();
9+
}

0 commit comments

Comments
 (0)