Skip to content

Commit 554fec7

Browse files
honokaBiuhonokaBiu
authored
Merge pull request onlyliuxin#16 from 592146505/master
update List and add BinaryTreeNode
2 parents dd5393b + 5245959 commit 554fec7

File tree

9 files changed

+303
-6
lines changed

9 files changed

+303
-6
lines changed

‎group20/592146505/data _structure/src/org/wsc/exception/NullElementException.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package org.wsc.exception;
2+
3+
/**
4+
*
5+
* 空元素异常
6+
* @author Administrator
7+
* @date 2017年2月26日下午4:15:49
8+
* @version v1.0
9+
*
10+
*/
11+
public class NullElementException extends RuntimeException {
12+
13+
private static final long serialVersionUID = 4729177529481680909L;
14+
15+
public NullElementException() {
16+
super();
17+
}
18+
19+
public NullElementException(String message) {
20+
super(message);
21+
}
22+
23+
}

‎group20/592146505/data _structure/src/org/wsc/exception/RepeatingElementException.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package org.wsc.exception;
2+
3+
/**
4+
*
5+
* 重复元素异常
6+
* @author Administrator
7+
* @date 2017年2月26日下午4:15:49
8+
* @version v1.0
9+
*
10+
*/
11+
public class RepeatingElementException extends RuntimeException {
12+
13+
private static final long serialVersionUID = 4729177529481680909L;
14+
15+
public RepeatingElementException() {
16+
super();
17+
}
18+
19+
public RepeatingElementException(String message) {
20+
super(message);
21+
}
22+
23+
}

‎group20/592146505/data _structure/src/cn/wsc/util/ArrayList.java renamed to ‎group20/592146505/data _structure/src/org/wsc/list/ArrayList.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package cn.wsc.util;
1+
package org.wsc.list;
22

33
import java.util.Arrays;
44
import java.util.ConcurrentModificationException;

‎group20/592146505/data _structure/src/org/wsc/list/Iterator.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package org.wsc.list;
2+
3+
public interface Iterator<E> {
4+
/**
5+
* 是否存在下一个元素
6+
* @return
7+
*/
8+
boolean hasNext();
9+
10+
/**
11+
* 获取下一个元素
12+
* @return
13+
*/
14+
E next();
15+
16+
/**
17+
* 删除当前元素
18+
*/
19+
void remove();
20+
21+
}

‎group20/592146505/data _structure/src/cn/wsc/util/LinkedList.java renamed to ‎group20/592146505/data _structure/src/org/wsc/list/LinkedList.java

Lines changed: 23 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,19 @@
1-
package cn.wsc.util;
1+
package org.wsc.list;
22

33
import java.util.ConcurrentModificationException;
44
import java.util.NoSuchElementException;
55

66
/**
77
* LinkedList类
8-
*
8+
* 实现List接口和Queue接口
9+
* 基于链表的集合
910
* @author Administrator
1011
* @date 2017年2月25日上午10:52:41
1112
* @version v1.0
1213
*
1314
* @param <E>
1415
*/
15-
public class LinkedList<E> implements List<E> {
16+
public class LinkedList<E> implements List<E>,Queue<E> {
1617

1718
private int size;
1819
Node<E> first; // 链表的头节点
@@ -224,6 +225,14 @@ public E remove(int index) {
224225
return unlink(node(index));
225226
}
226227

228+
public E removeFirst() {
229+
//获取头节点
230+
final Node<E> f = first;
231+
if (f == null)
232+
throw new NoSuchElementException();
233+
return remove(0);
234+
}
235+
227236
/**
228237
* 删除节点
229238
*
@@ -252,6 +261,16 @@ E unlink(Node<E> x) {
252261
return element;
253262
}
254263

264+
@Override
265+
public void enQueue(E e) {
266+
linkLast(e);
267+
}
268+
269+
@Override
270+
public E deQueue() {
271+
return removeFirst();
272+
}
273+
255274
/**
256275
* 位置范围检查 >0 && <=size
257276
*
@@ -281,4 +300,5 @@ private void checkElementIndex(int index) {
281300
private String outOfBoundsMsg(int index) {
282301
return "Index: " + index + ", Size: " + this.size;
283302
}
303+
284304
}

‎group20/592146505/data _structure/src/cn/wsc/util/List.java renamed to ‎group20/592146505/data _structure/src/org/wsc/list/List.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package cn.wsc.util;
1+
package org.wsc.list;
22

33
/**
44
* List接口

‎group20/592146505/data _structure/src/org/wsc/list/Queue.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package org.wsc.list;
2+
3+
/**
4+
*
5+
* 队列
6+
*
7+
* @author Administrator
8+
* @date 2017年2月25日下午6:08:01
9+
* @version v1.0
10+
*
11+
* @param <E>
12+
*/
13+
public interface Queue<E> {
14+
15+
/**
16+
* 入列
17+
*
18+
* @param e
19+
*/
20+
public void enQueue(E e);
21+
22+
/**
23+
* 出列
24+
*
25+
* @return
26+
*/
27+
public E deQueue();
28+
29+
/**
30+
* 是否为空
31+
*
32+
* @return
33+
*/
34+
public boolean isEmpty();
35+
36+
/**
37+
* 元素长度
38+
*
39+
* @return
40+
*/
41+
public int size();
42+
}

‎group20/592146505/data _structure/src/cn/wsc/utils/Stack.java renamed to ‎group20/592146505/data _structure/src/org/wsc/stack/Stack.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1-
package cn.wsc.utils;
1+
package org.wsc.stack;
2+
3+
import org.wsc.list.ArrayList;
24

35
public class Stack {
46
private ArrayList elementData = new ArrayList();

‎group20/592146505/data _structure/src/org/wsc/tree_node/BinaryTreeNode.java

Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
package org.wsc.tree_node;
2+
3+
import org.wsc.exception.NullElementException;
4+
import org.wsc.exception.RepeatingElementException;
5+
6+
/**
7+
* BinaryTreeNode 二叉树结构
8+
*
9+
*
10+
* @author Administrator
11+
* @date 2017年2月26日下午5:47:32
12+
* @version v1.0
13+
*
14+
* @param <E>
15+
* 必须实现Comparable接口
16+
*/
17+
@SuppressWarnings("rawtypes")
18+
public class BinaryTreeNode<E extends Comparable> {
19+
20+
/** 左节点 */
21+
private BinaryTreeNode<E> left;
22+
/** 数据区 */
23+
private E data;
24+
/** 右节点 */
25+
private BinaryTreeNode<E> right;
26+
27+
/**
28+
* 插入
29+
*
30+
* @param data
31+
* @return
32+
*/
33+
@SuppressWarnings("unchecked")
34+
public BinaryTreeNode<E> insert(E data) {
35+
if (data == null)
36+
throw new NullElementException("Do not insert a null");
37+
// 当前数据区为空,则将data放入数据区
38+
if (this.data == null) {
39+
this.data = data;
40+
return this;
41+
}
42+
// 对比当前数据区数据和data大小
43+
int result = this.data.compareTo(data);
44+
// 如果相等，则抛出异常
45+
if (result == 0)
46+
throw new RepeatingElementException("Do not insert duplicate element");
47+
// 当前数据区数据大于data，将data递归放入左节点
48+
if (result > 0) {
49+
// 左节点为空，则将数据置入左节点
50+
if (left == null)
51+
left = new BinaryTreeNode<E>(data);
52+
else// 左节点不为空，则将数据递归置入左节点
53+
left.insert(data);
54+
} else {
55+
// 右节点为空，则将数据置入右节点
56+
if (right == null)
57+
right = new BinaryTreeNode<E>(data);
58+
else// 右节点不为空，则将数据递归置入右节点
59+
right.insert(data);
60+
}
61+
return this;
62+
}
63+
64+
/**
65+
* 查询
66+
*
67+
* @param data
68+
* @return
69+
*/
70+
@SuppressWarnings("unchecked")
71+
public BinaryTreeNode<E> seek(E data) {
72+
checkCurrElement();
73+
if (data == null)
74+
return null;
75+
// 对比当前数据区数据和data大小
76+
int result = this.data.compareTo(data);
77+
if (result == 0) {
78+
return this;
79+
} else if (result > 0) {// 当前数据区数据大于data，递归对比左节点
80+
return left == null ? null : left.seek(data);
81+
} else {// 当前数据区数据小于data，递归对比右节点
82+
return right == null ? null : right.seek(data);
83+
}
84+
85+
}
86+
87+
/**
88+
* 删除
89+
*
90+
* @param data
91+
* @return
92+
*/
93+
public BinaryTreeNode<E> remove(E data) {
94+
return removeChild(null, data);
95+
}
96+
97+
@SuppressWarnings("unchecked")
98+
public BinaryTreeNode<E> removeChild(BinaryTreeNode<E> supNode, E data) {
99+
checkCurrElement();
100+
if (data == null)
101+
return null;
102+
// 对比当前数据区数据和data大小
103+
int result = this.data.compareTo(data);
104+
// 如果相同，将通过父节点将子节点引用置为null
105+
if (supNode != null && result == 0) {
106+
if (supNode.left == this)
107+
supNode.left = null;
108+
else
109+
supNode.right = null;
110+
} else if (result > 0) {// 当前数据区数据大于data，递归对比左节点
111+
return left == null ? null : left.removeChild(this, data);
112+
} else {// 当前数据区数据小于data，递归对比右节点
113+
return right == null ? null : right.removeChild(this, data);
114+
}
115+
return this;
116+
}
117+
118+
/**
119+
* 检查当前节点元素是否有效
120+
*/
121+
private void checkCurrElement() {
122+
if (this.data == null)
123+
throw new NullElementException("The current node element is null");
124+
}
125+
126+
public BinaryTreeNode() {
127+
super();
128+
}
129+
130+
public BinaryTreeNode(E data) {
131+
super();
132+
this.data = data;
133+
}
134+
135+
public BinaryTreeNode(BinaryTreeNode<E> left, E data, BinaryTreeNode<E> right) {
136+
super();
137+
this.left = left;
138+
this.data = data;
139+
this.right = right;
140+
}
141+
142+
public E getData() {
143+
return data;
144+
}
145+
146+
public void setData(E data) {
147+
this.data = data;
148+
}
149+
150+
public BinaryTreeNode<E> getLeft() {
151+
return left;
152+
}
153+
154+
public void setLeft(BinaryTreeNode<E> left) {
155+
this.left = left;
156+
}
157+
158+
public BinaryTreeNode<E> getRight() {
159+
return right;
160+
}
161+
162+
public void setRight(BinaryTreeNode<E> right) {
163+
this.right = right;
164+
}
165+
166+
}

0 commit comments

Comments
 (0)