Skip to content

Commit e33db9c

Browse files
zhiyuan0101zhiyuan0101
committed
...
1 parent d4a25d6 commit e33db9c

File tree

7 files changed

+448
-0
lines changed

7 files changed

+448
-0
lines changed

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

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package assignment;
2+
3+
public class BinaryTree {
4+
private BinaryTreeNode root;
5+
6+
public BinaryTree(Comparable data) {
7+
root = new BinaryTreeNode(data);
8+
}
9+
10+
public BinaryTree(BinaryTreeNode root) {
11+
this.root = root;
12+
}
13+
14+
public BinaryTreeNode insert(Comparable data) {
15+
BinaryTreeNode node = new BinaryTreeNode(data);
16+
if (root == null)
17+
root = node;
18+
else
19+
insert(root, node);
20+
return node;
21+
}
22+
23+
public BinaryTreeNode insert(BinaryTreeNode node) {
24+
return insert(node.getData());
25+
}
26+
27+
private void insert(BinaryTreeNode current, BinaryTreeNode node) {
28+
29+
if (current.compareTo(node) >= 0) {
30+
if (current.getLeft() == null)
31+
current.setLeft(node);
32+
else
33+
insert(current.getLeft(), node);
34+
}
35+
else {
36+
if (current.getRight() == null)
37+
current.setRight(node);
38+
else
39+
insert(current.getRight(), node);
40+
}
41+
}
42+
43+
@Override
44+
public String toString() {
45+
return new BFSNodeQueue().toString();
46+
}
47+
48+
/**
49+
* 广度优先遍历节点队列
50+
*
51+
* @author Administrator
52+
*
53+
*/
54+
private class BFSNodeQueue {
55+
private MyQueue nodeQueue;
56+
57+
public BFSNodeQueue() {
58+
nodeQueue = new MyQueue();
59+
enQueue(root);
60+
}
61+
62+
public boolean isEmpty() {
63+
return nodeQueue.isEmpty();
64+
}
65+
66+
public void enQueue(BinaryTreeNode node) {
67+
if (node != null) nodeQueue.enQueue(node);
68+
}
69+
70+
// 出队同时把子节点入队
71+
public BinaryTreeNode deQueue() {
72+
BinaryTreeNode first = (BinaryTreeNode) nodeQueue.deQueue();
73+
enQueue(first.getLeft());
74+
enQueue(first.getRight());
75+
return first;
76+
}
77+
78+
@Override
79+
public String toString() {
80+
StringBuilder stringBuilder = new StringBuilder();
81+
while (!nodeQueue.isEmpty()) {
82+
BinaryTreeNode binaryTreeNode = deQueue();
83+
stringBuilder.append(binaryTreeNode + "\n");
84+
}
85+
return stringBuilder.toString();
86+
}
87+
}
88+
89+
public static void main(String[] args) {
90+
BinaryTree binaryTree = new BinaryTree(4);
91+
binaryTree.insert(7);
92+
binaryTree.insert(8);
93+
System.out.println(binaryTree);
94+
}
95+
}

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

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

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

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

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

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

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

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
package assignment;
2+
3+
//
4+
public class MyLinkedList {
5+
private Node head;
6+
private int size;
7+
8+
public MyLinkedList() {
9+
size = 0;
10+
}
11+
12+
public void add(Object o) {
13+
if (head == null)
14+
addFirst(o);
15+
else
16+
addLast(o);
17+
}
18+
19+
public void addFirst(Object o) {
20+
Node oldFirst = head;
21+
head = new Node(o, oldFirst);
22+
size++;
23+
}
24+
25+
public void addLast(Object o) {
26+
if (head == null) {
27+
addFirst(o);
28+
}
29+
else {
30+
Node oldLast = movePtrTo(size - 1);
31+
oldLast.next = new Node(o, null);
32+
size++;
33+
}
34+
35+
}
36+
37+
public void add(int index, Object o) {
38+
rangeCheck(index - 1);
39+
if (index == 0) {
40+
addFirst(o);
41+
return;
42+
}
43+
Node temp = movePtrTo(index - 1);
44+
Node oldNext = temp.next;
45+
Node newNext = new Node(o, oldNext);
46+
temp.next = newNext;
47+
size++;
48+
}
49+
50+
public Object remove(int index) {
51+
rangeCheck(index);
52+
Object data;
53+
if (index == 0) {
54+
data = head.data;
55+
head = head.next;
56+
}
57+
else {
58+
Node pre = movePtrTo(index - 1);
59+
Node target = pre.next;
60+
pre.next = target.next;
61+
data = target.data;
62+
}
63+
size--;
64+
return data;
65+
}
66+
67+
public Object get(int index) {
68+
return movePtrTo(index).data;
69+
}
70+
71+
public int size() {
72+
return size;
73+
}
74+
75+
private Node movePtrTo(int index) {
76+
Node resultNode = head;
77+
for (int i = 0; i < index; i++) {
78+
resultNode = resultNode.next;
79+
}
80+
return resultNode;
81+
}
82+
83+
private void rangeCheck(int index) {
84+
if (index >= size) {
85+
throw new NoElementException("index:" + index);
86+
}
87+
}
88+
89+
@Override
90+
public String toString() {
91+
StringBuilder stringBuilder = new StringBuilder('[');
92+
Node temp = head;
93+
while (temp != null) {
94+
stringBuilder.append(String.valueOf(temp.toString()) + ",");
95+
temp = temp.next;
96+
}
97+
stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
98+
stringBuilder.append(']');
99+
return stringBuilder.toString();
100+
}
101+
102+
private static class Node {
103+
private Object data;
104+
private Node next;
105+
106+
public Node(Object data, Node next) {
107+
this.data = data;
108+
this.next = next;
109+
}
110+
111+
@Override
112+
public String toString() {
113+
return data.toString();
114+
}
115+
}
116+
}

0 commit comments

Comments
 (0)