Skip to content

Commit 05fc6ef

Browse files
luoziyihaoluoziyihao
authored
Merge pull request onlyliuxin#2 from 12378wzy/master
^_^
2 parents 71d6757 + 8872d60 commit 05fc6ef

File tree

13 files changed

+606
-0
lines changed

13 files changed

+606
-0
lines changed

‎group17/.gitignore

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
*.class
2+
3+
# Mobile Tools for Java (J2ME)
4+
.mtj.tmp/
5+
6+
# Package Files #
7+
*.jar
8+
*.war
9+
*.ear
10+
11+
# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
12+
hs_err_pid*
13+
14+
#ide config
15+
.metadata
16+
.recommenders

‎group17/1264835468/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group17/1264835468/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group17/1264835468/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>1264835468</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group17/1264835468/src/assignment/BinaryTree.java

Lines changed: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,154 @@
1+
package assignment;
2+
3+
//
4+
public class BinaryTree<T extends Comparable<? super T>> implements Iterable<BinaryTreeNode<T>> {
5+
private BinaryTreeNode<T> root;
6+
7+
public BinaryTree(T data) {
8+
root = new BinaryTreeNode<T>(data);
9+
}
10+
11+
public BinaryTree(BinaryTreeNode<T> root) {
12+
this.root = root;
13+
}
14+
15+
public BinaryTreeNode<T> insert(T data) {
16+
BinaryTreeNode<T> node = new BinaryTreeNode<T>(data);
17+
if (root == null)
18+
root = node;
19+
else
20+
insert(root, node);
21+
return node;
22+
}
23+
24+
public BinaryTreeNode<T> insert(BinaryTreeNode<T> node) {
25+
return insert(node.getData());
26+
}
27+
28+
private void insert(BinaryTreeNode<T> current, BinaryTreeNode<T> node) {
29+
30+
if (current.getData().compareTo(node.getData()) > 0) {
31+
if (current.getLeft() == null)
32+
current.setLeft(node);
33+
else
34+
insert(current.getLeft(), node);
35+
}
36+
else {
37+
if (current.getRight() == null)
38+
current.setRight(node);
39+
else
40+
insert(current.getRight(), node);
41+
}
42+
}
43+
44+
@Override
45+
public String toString() {
46+
return new BFSNodeQueue().toString();
47+
}
48+
49+
/**
50+
* 广度优先遍历节点队列
51+
*
52+
* @author Administrator
53+
*
54+
*/
55+
private class BFSNodeQueue {
56+
private MyQueue<BinaryTreeNode<T>> nodeQueue;
57+
58+
public BFSNodeQueue() {
59+
nodeQueue = new MyQueue<>();
60+
}
61+
62+
public boolean isEmpty() {
63+
return nodeQueue.isEmpty();
64+
}
65+
66+
public void enQueue(BinaryTreeNode<T> node) {
67+
if (node != null) nodeQueue.enQueue(node);
68+
}
69+
70+
// 出队同时把子节点入队
71+
public BinaryTreeNode<T> deQueue() {
72+
if (!isEmpty()) {
73+
BinaryTreeNode<T> first = nodeQueue.deQueue();
74+
enQueue(first.getLeft());
75+
enQueue(first.getRight());
76+
return first;
77+
}
78+
throw new QueueIsEmptyException();
79+
}
80+
81+
// 把所有出队节点放进另一个队列中
82+
public MyQueue<BinaryTreeNode<T>> getResult() {
83+
prepare();
84+
MyQueue<BinaryTreeNode<T>> result = new MyQueue<>();
85+
while (!isEmpty()) {
86+
result.enQueue(deQueue());
87+
}
88+
return result;
89+
}
90+
91+
private void prepare() {
92+
clearQueue();
93+
enQueue(root);
94+
}
95+
96+
public void clearQueue() {
97+
while (!isEmpty()) {
98+
deQueue();
99+
}
100+
}
101+
102+
@Override
103+
public String toString() {
104+
StringBuilder stringBuilder = new StringBuilder();
105+
106+
Iterator<BinaryTreeNode<T>> iterator = iterator();
107+
while (iterator.hasNext()) {
108+
stringBuilder.append(iterator.next() + "\n");
109+
}
110+
return stringBuilder.toString();
111+
}
112+
}
113+
114+
@Override
115+
public Iterator<BinaryTreeNode<T>> iterator() {
116+
return new BFSIterator();
117+
}
118+
119+
private class BFSIterator implements Iterator<BinaryTreeNode<T>> {
120+
MyArrayList<BinaryTreeNode<T>> list;
121+
Iterator<BinaryTreeNode<T>> iterator;
122+
123+
public BFSIterator() {
124+
MyQueue<BinaryTreeNode<T>> BFSQueue = new BFSNodeQueue().getResult();
125+
list = new MyArrayList<>();
126+
while (!BFSQueue.isEmpty()) {
127+
list.add(BFSQueue.deQueue());
128+
}
129+
iterator = list.iterator();
130+
}
131+
132+
@Override
133+
public boolean hasNext() {
134+
return iterator.hasNext();
135+
}
136+
137+
@Override
138+
public BinaryTreeNode<T> next() {
139+
return iterator.next();
140+
}
141+
}
142+
143+
public static void main(String[] args) {
144+
BinaryTree<Integer> binaryTree = new BinaryTree<>(5);
145+
binaryTree.insert(6);
146+
binaryTree.insert(7);
147+
binaryTree.insert(4);
148+
Iterator<BinaryTreeNode<Integer>> iterator = binaryTree.iterator();
149+
while (iterator.hasNext()) {
150+
System.out.println(iterator.next());
151+
}
152+
System.out.println(binaryTree);
153+
}
154+
}

‎group17/1264835468/src/assignment/BinaryTreeNode.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package assignment;
2+
3+
public class BinaryTreeNode<T extends Comparable<? super T>> {
4+
private T data;
5+
private BinaryTreeNode<T> left;
6+
private BinaryTreeNode<T> right;
7+
8+
public BinaryTreeNode(T data) {
9+
this.data = data;
10+
}
11+
12+
public T getData() {
13+
return data;
14+
}
15+
16+
public void setData(T data) {
17+
this.data = data;
18+
}
19+
20+
public BinaryTreeNode<T> getLeft() {
21+
return left;
22+
}
23+
24+
public void setLeft(BinaryTreeNode<T> left) {
25+
this.left = left;
26+
}
27+
28+
public BinaryTreeNode<T> getRight() {
29+
return right;
30+
}
31+
32+
public void setRight(BinaryTreeNode<T> right) {
33+
this.right = right;
34+
}
35+
36+
@Override
37+
public String toString() {
38+
StringBuilder stringBuilder = new StringBuilder();
39+
stringBuilder.append("node:" + data);
40+
// 非叶节点则加上左右子节点data
41+
if (left != null || right != null) {
42+
if (left != null)
43+
stringBuilder.append(",left:" + left.data);
44+
else
45+
stringBuilder.append(",left:null");
46+
if (right != null)
47+
stringBuilder.append(",right:" + right.data);
48+
else
49+
stringBuilder.append(",right:null");
50+
}
51+
return stringBuilder.toString();
52+
}
53+
54+
public static void main(String[] args) {
55+
// BinaryTreeNode<Integer> binaryTreeNode = new BinaryTreeNode<>(1);
56+
}
57+
58+
}

‎group17/1264835468/src/assignment/Iterable.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package assignment;
2+
3+
//
4+
public interface Iterable<T> {
5+
Iterator<T> iterator();
6+
}

‎group17/1264835468/src/assignment/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package assignment;
2+
3+
public interface Iterator<E> {
4+
public boolean hasNext();
5+
6+
public E next();
7+
}

‎group17/1264835468/src/assignment/List.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package assignment;
2+
3+
//
4+
public interface List<E> {
5+
public void add(E o);
6+
7+
public void add(int index, E o);
8+
9+
public E get(int index);
10+
11+
public E remove(int index);
12+
13+
public int size();
14+
}

‎group17/1264835468/src/assignment/MyArrayList.java

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
package assignment;
2+
3+
import java.util.Arrays;
4+
5+
public class MyArrayList<E> implements List<E>, Iterable<E> {
6+
private Object[] elementData;
7+
private static final int DEFAULT_SIZE = 10;
8+
private int size;
9+
10+
public MyArrayList() {
11+
this(DEFAULT_SIZE);
12+
}
13+
14+
public MyArrayList(int initSize) {
15+
if (initSize < 0) {
16+
throw new IllegalArgumentException(initSize + " < 0");
17+
}
18+
if (initSize == 0) {
19+
elementData = new Object[DEFAULT_SIZE];
20+
}
21+
else {
22+
elementData = new Object[initSize];
23+
}
24+
size = 0;
25+
}
26+
27+
public void add(E o) {
28+
growIfNeed();
29+
elementData[size++] = o;
30+
}
31+
32+
public void add(int index, E o) {
33+
if (index < 0 || index > size) {
34+
throw new IllegalArgumentException("index:" + index);
35+
}
36+
growIfNeed();
37+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
38+
elementData[index] = o;
39+
size++;
40+
}
41+
42+
@SuppressWarnings("unchecked")
43+
public E get(int index) {
44+
rangeCheck(index);
45+
return (E) elementData[index];
46+
}
47+
48+
public E remove(int index) {
49+
rangeCheck(index);
50+
E target = get(index);
51+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
52+
size--;
53+
return target;
54+
}
55+
56+
public int size() {
57+
return size;
58+
}
59+
60+
private void rangeCheck(int index) {
61+
if (index >= size) {
62+
throw new NoSuchElementException("index:" + index);
63+
}
64+
}
65+
66+
private void growIfNeed() {
67+
if (size == elementData.length)
68+
grow();
69+
}
70+
71+
private void grow() {
72+
elementData = Arrays.copyOf(elementData, elementData.length * 2);
73+
}
74+
75+
@Override
76+
public Iterator<E> iterator() {
77+
return new ArrayIterator<>();
78+
}
79+
80+
private class ArrayIterator<E> implements Iterator<E> {
81+
private int currentPos = 0;
82+
83+
@Override
84+
public boolean hasNext() {
85+
return currentPos < size;
86+
}
87+
88+
@SuppressWarnings("unchecked")
89+
@Override
90+
public E next() {
91+
rangeCheck(currentPos);
92+
return (E) elementData[currentPos++];
93+
}
94+
95+
}
96+
97+
@Override
98+
public String toString() {
99+
return Arrays.toString(Arrays.copyOf(elementData, size));
100+
}
101+
102+
}
103+
104+
class NoSuchElementException extends RuntimeException {
105+
106+
public NoSuchElementException(String string) {
107+
super(string);
108+
}
109+
110+
}

0 commit comments

Comments
 (0)