Skip to content

Commit 3f7749d

Browse files
zhiyuan0101zhiyuan0101
committed
。。。
1 parent e33db9c commit 3f7749d

File tree

7 files changed

+176
-93
lines changed

7 files changed

+176
-93
lines changed

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

Lines changed: 70 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,32 @@
11
package assignment;
22

3-
public class BinaryTree {
4-
private BinaryTreeNode root;
3+
public class BinaryTree<T extends Comparable<? super T>> implements Iterable<BinaryTreeNode<T>> {
4+
private BinaryTreeNode<T> root;
55

6-
public BinaryTree(Comparable data) {
7-
root = new BinaryTreeNode(data);
6+
public BinaryTree(T data) {
7+
root = new BinaryTreeNode<T>(data);
88
}
99

10-
public BinaryTree(BinaryTreeNode root) {
10+
public BinaryTree(BinaryTreeNode<T> root) {
1111
this.root = root;
1212
}
1313

14-
public BinaryTreeNode insert(Comparable data) {
15-
BinaryTreeNode node = new BinaryTreeNode(data);
14+
public BinaryTreeNode<T> insert(T data) {
15+
BinaryTreeNode<T> node = new BinaryTreeNode<T>(data);
1616
if (root == null)
1717
root = node;
1818
else
1919
insert(root, node);
2020
return node;
2121
}
2222

23-
public BinaryTreeNode insert(BinaryTreeNode node) {
23+
public BinaryTreeNode<T> insert(BinaryTreeNode<T> node) {
2424
return insert(node.getData());
2525
}
2626

27-
private void insert(BinaryTreeNode current, BinaryTreeNode node) {
27+
private void insert(BinaryTreeNode<T> current, BinaryTreeNode<T> node) {
2828

29-
if (current.compareTo(node) >= 0) {
29+
if (current.getData().compareTo(node.getData()) >= 0) {
3030
if (current.getLeft() == null)
3131
current.setLeft(node);
3232
else
@@ -52,44 +52,90 @@ public String toString() {
5252
*
5353
*/
5454
private class BFSNodeQueue {
55-
private MyQueue nodeQueue;
55+
private MyQueue<BinaryTreeNode<T>> nodeQueue;
5656

5757
public BFSNodeQueue() {
58-
nodeQueue = new MyQueue();
59-
enQueue(root);
58+
nodeQueue = new MyQueue<>();
6059
}
6160

6261
public boolean isEmpty() {
6362
return nodeQueue.isEmpty();
6463
}
6564

66-
public void enQueue(BinaryTreeNode node) {
65+
public void enQueue(BinaryTreeNode<T> node) {
6766
if (node != null) nodeQueue.enQueue(node);
6867
}
6968

7069
// 出队同时把子节点入队
71-
public BinaryTreeNode deQueue() {
72-
BinaryTreeNode first = (BinaryTreeNode) nodeQueue.deQueue();
73-
enQueue(first.getLeft());
74-
enQueue(first.getRight());
75-
return first;
70+
public BinaryTreeNode<T> deQueue() {
71+
if (!isEmpty()) {
72+
BinaryTreeNode<T> first = nodeQueue.deQueue();
73+
enQueue(first.getLeft());
74+
enQueue(first.getRight());
75+
return first;
76+
}
77+
throw new QueueIsEmptyException();
78+
}
79+
80+
public MyQueue<BinaryTreeNode<T>> getBFSNodeQueue() {
81+
prepare();
82+
MyQueue<BinaryTreeNode<T>> result = new MyQueue<>();
83+
while (!isEmpty()) {
84+
result.enQueue(deQueue());
85+
}
86+
return result;
87+
}
88+
89+
public void clearQueue() {
90+
while (!isEmpty()) {
91+
deQueue();
92+
}
93+
}
94+
95+
private void prepare() {
96+
clearQueue();
97+
enQueue(root);
7698
}
7799

78100
@Override
79101
public String toString() {
80102
StringBuilder stringBuilder = new StringBuilder();
81-
while (!nodeQueue.isEmpty()) {
82-
BinaryTreeNode binaryTreeNode = deQueue();
83-
stringBuilder.append(binaryTreeNode + "\n");
103+
Iterator<BinaryTreeNode<T>> iterator = iterator();
104+
while (iterator.hasNext()) {
105+
stringBuilder.append(iterator.next() + "\n");
84106
}
85107
return stringBuilder.toString();
86108
}
87109
}
88110

111+
@Override
112+
public Iterator<BinaryTreeNode<T>> iterator() {
113+
return new BFSIterator();
114+
}
115+
116+
private class BFSIterator implements Iterator<BinaryTreeNode<T>> {
117+
MyQueue<BinaryTreeNode<T>> BFSQueue = new BFSNodeQueue().getBFSNodeQueue();
118+
119+
@Override
120+
public boolean hasNext() {
121+
return !BFSQueue.isEmpty();
122+
}
123+
124+
@Override
125+
public BinaryTreeNode<T> next() {
126+
return BFSQueue.deQueue();
127+
}
128+
}
129+
89130
public static void main(String[] args) {
90-
BinaryTree binaryTree = new BinaryTree(4);
131+
BinaryTree<Integer> binaryTree = new BinaryTree<>(5);
132+
binaryTree.insert(6);
91133
binaryTree.insert(7);
92-
binaryTree.insert(8);
134+
binaryTree.insert(4);
135+
Iterator<BinaryTreeNode<Integer>> iterator = binaryTree.iterator();
136+
while (iterator.hasNext()) {
137+
System.out.println(iterator.next());
138+
}
93139
System.out.println(binaryTree);
94140
}
95141
}

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

Lines changed: 16 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,39 @@
11
package assignment;
22

33
//
4-
public class BinaryTreeNode implements Comparable<BinaryTreeNode> {
5-
private Comparable data;
6-
private BinaryTreeNode left;
7-
private BinaryTreeNode right;
4+
public class BinaryTreeNode<T extends Comparable<? super T>> {
5+
private T data;
6+
private BinaryTreeNode<T> left;
7+
private BinaryTreeNode<T> right;
88

9-
public BinaryTreeNode(Comparable data) {
9+
public BinaryTreeNode(T data) {
1010
this.data = data;
1111
}
1212

13-
public Comparable getData() {
13+
public T getData() {
1414
return data;
1515
}
1616

17-
public void setData(Comparable data) {
17+
public void setData(T data) {
1818
this.data = data;
1919
}
2020

21-
public BinaryTreeNode getLeft() {
21+
public BinaryTreeNode<T> getLeft() {
2222
return left;
2323
}
2424

25-
public void setLeft(BinaryTreeNode left) {
25+
public void setLeft(BinaryTreeNode<T> left) {
2626
this.left = left;
2727
}
2828

29-
public BinaryTreeNode getRight() {
29+
public BinaryTreeNode<T> getRight() {
3030
return right;
3131
}
3232

33-
public void setRight(BinaryTreeNode right) {
33+
public void setRight(BinaryTreeNode<T> right) {
3434
this.right = right;
3535
}
3636

37-
@Override
38-
public int compareTo(BinaryTreeNode o) {
39-
return data.compareTo(o.data);
40-
}
41-
4237
@Override
4338
public String toString() {
4439
StringBuilder stringBuilder = new StringBuilder();
@@ -56,4 +51,9 @@ public String toString() {
5651
}
5752
return stringBuilder.toString();
5853
}
54+
55+
public static void main(String[] args) {
56+
// BinaryTreeNode<Integer> binaryTreeNode = new BinaryTreeNode<>(1);
57+
}
58+
5959
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
package assignment;
22

33
//
4-
public interface Iterator {
4+
public interface Iterator<E> {
55
public boolean hasNext();
66

7-
public Object next();
7+
public E next();
88
}

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

Lines changed: 27 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
//
44
import java.util.Arrays;
55

6-
public class MyArrayList {
6+
public class MyArrayList<E> implements List<E>, Iterable<E> {
77
private Object[] elementData;
88
private static final int DEFAULT_SIZE = 10;
99
private int size;
@@ -13,7 +13,8 @@ public MyArrayList() {
1313
}
1414

1515
public MyArrayList(int initSize) {
16-
if (initSize <= DEFAULT_SIZE) {
16+
if (initSize < 0) throw new IllegalArgumentException(initSize + " < 0");
17+
if (initSize == 0) {
1718
elementData = new Object[DEFAULT_SIZE];
1819
}
1920
else {
@@ -22,26 +23,27 @@ public MyArrayList(int initSize) {
2223
size = 0;
2324
}
2425

25-
public void add(Object o) {
26+
public void add(E o) {
2627
growIfNeed();
2728
elementData[size++] = o;
2829
}
2930

30-
public void add(int index, Object o) {
31+
public void add(int index, E o) {
3132
growIfNeed();
3233
System.arraycopy(elementData, index, elementData, index + 1, size - index);
3334
elementData[index] = o;
3435
size++;
3536
}
3637

37-
public Object get(int index) {
38+
@SuppressWarnings("unchecked")
39+
public E get(int index) {
3840
rangeCheck(index);
39-
return elementData[index];
41+
return (E) elementData[index];
4042
}
4143

42-
public Object remove(int index) {
44+
public E remove(int index) {
4345
rangeCheck(index);
44-
Object target = get(index);
46+
E target = get(index);
4547
// moveForwardFrom(index + 1);
4648
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
4749
size--;
@@ -66,17 +68,26 @@ private void grow() {
6668
elementData = Arrays.copyOf(elementData, elementData.length * 2);
6769
}
6870

69-
private void moveBackwardFrom(int index) {
70-
for (int i = size - 1; i >= index; i--) {
71-
elementData[i + 1] = elementData[i];
72-
}
71+
@Override
72+
public Iterator<E> iterator() {
73+
return new ArrayIterator<>();
7374
}
7475

75-
private void moveForwardFrom(int index) {
76-
for (int i = index; i < size; i++) {
77-
elementData[i - 1] = elementData[i];
76+
private class ArrayIterator<E> implements Iterator<E> {
77+
private int currentPos = 0;
78+
79+
@Override
80+
public boolean hasNext() {
81+
return currentPos < size;
7882
}
79-
elementData[size] = null;
83+
84+
@SuppressWarnings("unchecked")
85+
@Override
86+
public E next() {
87+
rangeCheck(currentPos);
88+
return (E) elementData[currentPos++];
89+
}
90+
8091
}
8192

8293
@Override

0 commit comments

Comments
 (0)