Skip to content

Commit 3dd4ea9

Browse files
zjhylovezjhylove
committed
二叉树实现更新以及单元测试
1 parent 77348a7 commit 3dd4ea9

File tree

6 files changed

+399
-181
lines changed

6 files changed

+399
-181
lines changed

‎group12/2258659044/zj-2017/src/com/coding/basic/ArrayList.java

Lines changed: 100 additions & 100 deletions
Original file line numberDiff line numberDiff line change
@@ -1,100 +1,100 @@
1-
package com.coding.basic;
2-
3-
import java.util.NoSuchElementException;
4-
5-
public class ArrayList implements List {
6-
7-
private int size = 0;
8-
/*扩容因子*/
9-
private static final int GENE = 10;
10-
11-
private Object[] elementData = new Object[10];
12-
/*扩容引用*/
13-
private Object[] newElementData;
14-
15-
public void add(Object o){
16-
if(size>=elementData.length){//扩容
17-
grow();
18-
}
19-
elementData[size] = o;
20-
size ++;
21-
}
22-
public void add(int index, Object o){
23-
24-
if(index>size){
25-
throw new IndexOutOfBoundsException("Index: "+index+",Size:"+size);
26-
}
27-
if(size>=elementData.length||index>=elementData.length-1){//长度不够需要扩容
28-
grow();
29-
}
30-
if(index<size){//长度足够需要移动
31-
newElementData = new Object[elementData.length];
32-
System.arraycopy(elementData, 0, newElementData, 0, index);
33-
System.arraycopy(elementData, index, newElementData, index+1, size-index);
34-
elementData = newElementData;
35-
}
36-
elementData[index] = o;
37-
if(index>size){
38-
size = index+1;
39-
}else{
40-
size ++;
41-
}
42-
}
43-
44-
public Object get(int index){
45-
46-
if(index>=size){
47-
throw new IndexOutOfBoundsException("Index: "+index+",Size:"+size);
48-
}
49-
return elementData[index];
50-
}
51-
52-
public Object remove(int index){
53-
54-
Object o = elementData[index];
55-
System.arraycopy(elementData, index+1, elementData, index, size-(index+1));
56-
size --;
57-
return o;
58-
}
59-
60-
public int size(){
61-
return size;
62-
}
63-
64-
/**
65-
* 扩容，扩容因子为10
66-
*/
67-
private void grow(){
68-
69-
newElementData = new Object[size+GENE];
70-
System.arraycopy(elementData, 0, newElementData, 0, elementData.length);
71-
elementData = newElementData;
72-
}
73-
74-
75-
public Iterator iterator(){
76-
77-
return new Itr();
78-
}
79-
80-
private class Itr implements Iterator{
81-
82-
int cursor;
83-
@Override
84-
public boolean hasNext() {
85-
return cursor != ArrayList.this.size;
86-
}
87-
88-
@Override
89-
public Object next() {
90-
91-
int i = this.cursor;
92-
if (i >= ArrayList.this.size){
93-
throw new NoSuchElementException();
94-
}
95-
this.cursor = (i + 1);
96-
return ArrayList.this.elementData[i];
97-
}
98-
99-
}
100-
}
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
/*扩容因子*/
9+
private static final int GENE = 10;
10+
11+
private Object[] elementData = new Object[10];
12+
/*扩容引用*/
13+
private Object[] newElementData;
14+
15+
public void add(Object o){
16+
if(size>=elementData.length){//扩容
17+
grow();
18+
}
19+
elementData[size] = o;
20+
size ++;
21+
}
22+
public void add(int index, Object o){
23+
24+
if(index>size){
25+
throw new IndexOutOfBoundsException("Index: "+index+",Size:"+size);
26+
}
27+
if(size>=elementData.length||index>=elementData.length-1){//长度不够需要扩容
28+
grow();
29+
}
30+
if(index<size){//长度足够需要移动
31+
newElementData = new Object[elementData.length];
32+
System.arraycopy(elementData, 0, newElementData, 0, index);
33+
System.arraycopy(elementData, index, newElementData, index+1, size-index);
34+
elementData = newElementData;
35+
}
36+
elementData[index] = o;
37+
if(index>size){
38+
size = index+1;
39+
}else{
40+
size ++;
41+
}
42+
}
43+
44+
public Object get(int index){
45+
46+
if(index>size){
47+
throw new IndexOutOfBoundsException("Index: "+index+",Size:"+size);
48+
}
49+
return elementData[index];
50+
}
51+
52+
public Object remove(int index){
53+
54+
Object o = elementData[index];
55+
System.arraycopy(elementData, index+1, elementData, index, size-(index+1));
56+
size --;
57+
return o;
58+
}
59+
60+
public int size(){
61+
return size;
62+
}
63+
64+
/**
65+
* 扩容，扩容因子为10
66+
*/
67+
private void grow(){
68+
69+
newElementData = new Object[size+GENE];
70+
System.arraycopy(elementData, 0, newElementData, 0, elementData.length);
71+
elementData = newElementData;
72+
}
73+
74+
75+
public Iterator iterator(){
76+
77+
return new Itr();
78+
}
79+
80+
private class Itr implements Iterator{
81+
82+
int cursor;
83+
@Override
84+
public boolean hasNext() {
85+
return cursor != ArrayList.this.size;
86+
}
87+
88+
@Override
89+
public Object next() {
90+
91+
int i = this.cursor;
92+
if (i >= ArrayList.this.size){
93+
throw new NoSuchElementException();
94+
}
95+
this.cursor = (i + 1);
96+
return ArrayList.this.elementData[i];
97+
}
98+
99+
}
100+
}

‎group12/2258659044/zj-2017/src/com/coding/basic/BinaryTree.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTree {
4+
5+
//根节点
6+
private BinaryTreeNode root;
7+
8+
@SuppressWarnings({ "rawtypes", "unchecked" })
9+
public <T extends Comparable<? super T>> BinaryTreeNode insert(T o){
10+
11+
BinaryTreeNode treeNode = new BinaryTreeNode();
12+
treeNode.setData(o);
13+
if(root == null){
14+
root = treeNode;
15+
}else{
16+
BinaryTreeNode currentNode = root;
17+
BinaryTreeNode parent;
18+
while(true){
19+
parent = currentNode;
20+
if(((Comparable)currentNode.getData()).compareTo(o)>0){//向左放
21+
currentNode = currentNode.getLeft();
22+
if(currentNode == null){
23+
parent.setLeft(treeNode);
24+
treeNode.setParent(parent);
25+
break;
26+
}
27+
}else{//向右放
28+
currentNode = currentNode.getRight();
29+
if(currentNode == null){
30+
parent.setRight(treeNode);
31+
treeNode.setParent(parent);
32+
break;
33+
}
34+
}
35+
}
36+
}
37+
return treeNode;
38+
}
39+
40+
/**
41+
* 先序遍历
42+
* @param node
43+
* @return
44+
*/
45+
public List traversalBefore(BinaryTreeNode node){
46+
//所有数据集合
47+
List datas = new ArrayList();
48+
return traversal(node,datas);
49+
}
50+
private List traversal(BinaryTreeNode node,List datas){
51+
52+
if(node !=null){
53+
datas.add(node.getData());
54+
traversal(node.getLeft(),datas);
55+
traversal(node.getRight(),datas);
56+
}
57+
return datas;
58+
}
59+
60+
public BinaryTreeNode getRoot() {
61+
return root;
62+
}
63+
64+
}

‎group12/2258659044/zj-2017/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 37 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -1,81 +1,37 @@
1-
package com.coding.basic;
2-
public class BinaryTreeNode {
3-
4-
private Object data;
5-
//根节点
6-
private BinaryTreeNode root;
7-
//父节点
8-
private BinaryTreeNode parent;
9-
private BinaryTreeNode left;
10-
private BinaryTreeNode right;
11-
//所有数据集合
12-
private final List datas = new ArrayList();
13-
public Object getData() {
14-
return data;
15-
}
16-
public void setData(Object data) {
17-
this.data = data;
18-
}
19-
public BinaryTreeNode getLeft() {
20-
return left;
21-
}
22-
public void setLeft(BinaryTreeNode left) {
23-
this.left = left;
24-
}
25-
public BinaryTreeNode getRight() {
26-
return right;
27-
}
28-
public void setRight(BinaryTreeNode right) {
29-
this.right = right;
30-
}
31-
32-
@SuppressWarnings({ "rawtypes", "unchecked" })
33-
public <T extends Comparable<? super T>> BinaryTreeNode insert(T o){
34-
35-
BinaryTreeNode treeNode = new BinaryTreeNode();
36-
treeNode.data = o;
37-
if(root == null){
38-
root = treeNode;
39-
root.root = treeNode;
40-
}else{
41-
BinaryTreeNode currentNode = root;
42-
while(true){
43-
parent = currentNode;
44-
if(((Comparable)currentNode.data).compareTo(o)>0){//向左放
45-
currentNode = currentNode.getLeft();
46-
if(currentNode == null){
47-
parent.left = treeNode;
48-
treeNode.parent = parent;
49-
treeNode.root = root;
50-
break;
51-
}
52-
}else{//向右放
53-
currentNode = currentNode.getRight();
54-
if(currentNode == null){
55-
parent.right = treeNode;
56-
treeNode.parent = parent;
57-
treeNode.root = root;
58-
break;
59-
}
60-
}
61-
}
62-
}
63-
return treeNode;
64-
}
65-
66-
/**
67-
* 先序遍历
68-
* @param node
69-
* @return
70-
*/
71-
public List traversal(BinaryTreeNode node){
72-
73-
if(node !=null){
74-
datas.add(node.data);
75-
traversal(node.left);
76-
traversal(node.right);
77-
}
78-
return datas;
79-
}
80-
81-
}
1+
package com.coding.basic;
2+
public class BinaryTreeNode {
3+
4+
private Object data;
5+
//父节点
6+
private BinaryTreeNode parent;
7+
private BinaryTreeNode left;
8+
private BinaryTreeNode right;
9+
10+
public Object getData() {
11+
return data;
12+
}
13+
public void setData(Object data) {
14+
this.data = data;
15+
}
16+
17+
public BinaryTreeNode getLeft() {
18+
return left;
19+
}
20+
public void setLeft(BinaryTreeNode left) {
21+
this.left = left;
22+
}
23+
24+
public BinaryTreeNode getRight() {
25+
return right;
26+
}
27+
public void setRight(BinaryTreeNode right) {
28+
this.right = right;
29+
}
30+
31+
public BinaryTreeNode getParent() {
32+
return parent;
33+
}
34+
public void setParent(BinaryTreeNode parent) {
35+
this.parent = parent;
36+
}
37+
}

0 commit comments

Comments
 (0)