Skip to content

Commit 692b812

Browse files
harryhookharryhook
committed
Add my first code v1.0
BinaryTreeNode has a bug
1 parent 4550485 commit 692b812

File tree

8 files changed

+317
-19
lines changed

8 files changed

+317
-19
lines changed

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/ArrayListTest.java

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,8 @@
77
public class ArrayListTest extends ListTest {
88

99
@Before
10-
public void setUpArrayList() {
10+
public void setUpArrayList()
11+
{
1112
aList = new MyArrayList();
1213
}
1314

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/BinaryTreeNode.java

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
/*
2+
* Created by Harry 2017-2-23 10:50:39
3+
* 实现二叉树,并按二叉查找树插入节点
4+
* 能实现基本的功能，但测试时存在问题，传进去的数据为空 2017-2-2523:49:43
5+
*/
6+
package com.github.HarryHook.coding2017.basic;
7+
8+
public class BinaryTreeNode
9+
{
10+
private Integer data;
11+
private BinaryTreeNode left;
12+
private BinaryTreeNode right;
13+
14+
//中序遍历二叉树
15+
public void inOrder(BinaryTreeNode node)
16+
{
17+
if(node != null)
18+
{
19+
inOrder(node.left);
20+
System.out.print(" " + node.data);
21+
inOrder(node.right);
22+
}
23+
}
24+
25+
//获取给节点的值
26+
public Integer getData()
27+
{
28+
return this.data;
29+
}
30+
//给一个节点赋值
31+
public void setData(Integer data)
32+
{
33+
this.data = data;
34+
}
35+
//获取左节点
36+
public BinaryTreeNode getLeft()
37+
{
38+
return left;
39+
}
40+
//指定左节点
41+
public void setLeft(BinaryTreeNode left)
42+
{
43+
this.left = left;
44+
}
45+
46+
//获取右节点
47+
public BinaryTreeNode getRight()
48+
{
49+
return right;
50+
}
51+
//指定右节点
52+
public void setRight(BinaryTreeNode right)
53+
{
54+
this.right = right;
55+
}
56+
57+
//在二叉树中插入一个节点，需要判断
58+
public BinaryTreeNode insert(Integer obj)
59+
{
60+
// 新增节点
61+
BinaryTreeNode newNode = new BinaryTreeNode();
62+
// 当前节点,保留根的值
63+
BinaryTreeNode current = this;
64+
// 上个节点
65+
BinaryTreeNode parent = null;
66+
// 如果根节点为空
67+
if (this.data == null)
68+
{
69+
newNode.setData(obj);
70+
newNode.setLeft(null);
71+
newNode.setRight(null);
72+
return newNode;
73+
}else
74+
{
75+
while (true)
76+
{
77+
parent = current;
78+
if (obj < current.data)
79+
{
80+
current = current.left;
81+
if (current == null)
82+
{
83+
newNode.setData(obj);
84+
newNode.setLeft(null);
85+
newNode.setRight(null);
86+
parent.left = newNode;
87+
return newNode;
88+
}
89+
} else
90+
{
91+
current = current.right;
92+
if (current == null)
93+
{
94+
newNode.setData(obj);
95+
newNode.setLeft(null);
96+
newNode.setRight(null);
97+
parent.right = newNode;
98+
return newNode;
99+
}
100+
}
101+
}
102+
}
103+
}
104+
105+
public static void main(String[] args)
106+
{
107+
BinaryTreeNode BTN = new BinaryTreeNode();
108+
109+
BTN = BTN.insert(5);
110+
System.out.print(BTN.getData() + " ");
111+
System.out.print(BTN.insert(2).getData() + " ");
112+
System.out.print(BTN.insert(1).getData() + " ");
113+
System.out.print(BTN.insert(4).getData() + " ");
114+
System.out.print(BTN.insert(6).getData() + " ");
115+
System.out.print(BTN.insert(8).getData() + " ");
116+
System.out.println("");
117+
System.out.println("中序遍历二叉树： ");
118+
BTN.inOrder(BTN);
119+
}
120+
121+
}

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/BinaryTreeNodeTest.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.github.HarryHook.coding2017.basic;
2+
3+
import static org.junit.Assert.assertEquals;
4+
5+
import org.junit.Before;
6+
import org.junit.Test;
7+
8+
import com.github.HarryHook.coding2017.basic.BinaryTreeNode;
9+
10+
public class BinaryTreeNodeTest
11+
{
12+
13+
BinaryTreeNode binaryTreeNode = new BinaryTreeNode();
14+
15+
@Before
16+
public void setUpBinaryTreeNode()
17+
{
18+
//binaryTreeNode = new BinaryTreeNode();
19+
}
20+
21+
@Test
22+
public void testBinaryTreeNodeFunctional()
23+
{
24+
binaryTreeNode.insert(4);
25+
binaryTreeNode.insert(1);
26+
binaryTreeNode.insert(3);
27+
binaryTreeNode.insert(5);
28+
binaryTreeNode.insert(2);
29+
30+
assertEquals(true, 4 == binaryTreeNode.getData());
31+
assertEquals(true, 1 == binaryTreeNode.getLeft().getData());
32+
assertEquals(true, 5 == binaryTreeNode.getRight().getData());
33+
assertEquals(true, 3 == binaryTreeNode.getLeft().getRight().getData());
34+
assertEquals(true, 2 == binaryTreeNode.getLeft().getRight().getLeft().getData());
35+
36+
//节点为空 说明值没有插进去
37+
binaryTreeNode.inOrder(binaryTreeNode);
38+
}
39+
40+
}

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/LinkedListTest.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ public void testLinkedListFunctional() {
7777
assertEquals(5, aLinkedList.size());
7878
assertEquals(5, aLinkedList.get(0));
7979
assertEquals(1, aLinkedList.get(2));
80-
assertEquals(4, aLinkedList.get(3));
80+
assertEquals(0, aLinkedList.get(3));
8181

8282
aLinkedList.remove(3); // [5, 4, 1, 3]
8383
assertEquals(3, aLinkedList.get(aLinkedList.size()-1));

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/ListTest.java

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -88,9 +88,9 @@ public void testException() {
8888
}
8989

9090
@Test
91-
//protected static List aList;
9291

93-
public void testIterator() {
92+
public void testIterator()
93+
{
9494
Iterator it = aList.iterator();
9595
assertEquals(false, it.hasNext());
9696

@@ -111,6 +111,10 @@ public void testIterator() {
111111
assertEquals(1, it.next());
112112
assertEquals(3, it.next());
113113
assertEquals(false, it.hasNext());
114+
115+
expectedEx.expect(Exception.class);
116+
it.next();
117+
114118
}
115119

116120

‎group02/727171008/src/com/github/HarryHook/coding2017/basic/MyArrayList.java

Lines changed: 23 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
package com.github.HarryHook.coding2017.basic;
66

77
import java.util.Arrays;
8+
import java.util.NoSuchElementException;
89

910
public class MyArrayList implements List
1011
{
@@ -40,6 +41,7 @@ public void add(int index, Object o)
4041
elementData[index] = o;
4142
}
4243
size++;
44+
4345
/*
4446
//判断索引位置是否正确
4547
if (index > size || index < 0)
@@ -62,8 +64,12 @@ public void add(int index, Object o)
6264
}
6365

6466
public Object get(int index)
65-
{
67+
{
68+
//若index超出size应该抛出异常
69+
if(index >= size)
70+
throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + size);
6671
return elementData[index];
72+
6773
}
6874

6975
public Object remove(int index)
@@ -83,7 +89,7 @@ public void ensureCapacity(int minCapacity)
8389
int oldCapacity = elementData.length;
8490
if (minCapacity > oldCapacity)
8591
{
86-
Object oldData[] = elementData; //防止copyof()执行的过程中新内存或者其他进程分配内存时占用旧内存
92+
//Object oldData[] = elementData; //防止copyof()执行的过程中新内存或者其他进程分配内存时占用旧内存
8793
int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1
8894
if (newCapacity < minCapacity)
8995
newCapacity = minCapacity;
@@ -112,25 +118,33 @@ public boolean hasNext()
112118
}
113119
public Object next()
114120
{
115-
Object next = get(cursor);
116-
cursor ++;
117-
return next;
121+
try {
122+
Object next = get(cursor);
123+
cursor++;
124+
return next;
125+
126+
} catch (IndexOutOfBoundsException e)
127+
{
128+
throw new NoSuchElementException();
129+
}
130+
118131
}
119132
}
120133

121134
public static void main(String[] args)
122135
{
123136
MyArrayList myArrays = new MyArrayList();
124-
125-
for(int i = 0; i < 19; i++)
126-
myArrays.add(i, 55);
127-
128137
myArrays.add(3);
129138
myArrays.add(0, 11);
130139
myArrays.add(1, 2);
131140
myArrays.add(3, 5);
132141
myArrays.add(2, 1);
133142
myArrays.add(7);
143+
Print(myArrays);
144+
145+
for(int i = 0; i < 19; i++)
146+
myArrays.add(i, 55);
147+
134148
System.out.println("获取指定位置元素： " + myArrays.get(2));
135149
System.out.println("删除指定位置元素： " + myArrays.remove(1));
136150
System.out.println("当前元素个数：" + myArrays.size());

‎liuxin/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 87 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,51 @@
11
package com.coding.basic;
22

3-
public class BinaryTreeNode {
4-
5-
private Object data;
6-
private BinaryTreeNode left;
7-
private BinaryTreeNode right;
8-
3+
public class BinaryTreeNode
4+
{
5+
public static TreeNode root; //根节点
6+
public BinaryTreeNode()
7+
{
8+
this.root = null;
9+
}
10+
public TreeNode insert (int key)
11+
{
12+
// 新增节点
13+
TreeNode newNode = new TreeNode(key);
14+
// 当前节点
15+
TreeNode current = root;
16+
// 上个节点
17+
TreeNode parent = null;
18+
// 如果根节点为空
19+
if (current == null)
20+
{
21+
root = newNode;
22+
return newNode;
23+
}
24+
while (true)
25+
{
26+
parent = current;
27+
if (key < current.value)
28+
{
29+
current = current.left;
30+
if (current == null)
31+
{
32+
parent.left = newNode;
33+
return newNode;
34+
}
35+
} else
36+
{
37+
current = current.right;
38+
if (current == null)
39+
{
40+
parent.right = newNode;
41+
return newNode;
42+
}
43+
}
44+
}
45+
}
46+
47+
}
48+
949
public Object getData() {
1050
return data;
1151
}
@@ -30,3 +70,44 @@ public BinaryTreeNode insert(Object o){
3070
}
3171

3272
}
73+
74+
class TreeNode //树的节点
75+
{
76+
int value;
77+
TreeNode left;
78+
TreeNode right;
79+
80+
public TreeNode(int value)
81+
{
82+
this.value = value;
83+
left = null;
84+
right = null;
85+
}
86+
}
87+
88+
public class BinaryTreeNodeTest {
89+
90+
public static void main(String[] args) {
91+
BinaryTreeNode b = new BinaryTreeNode();
92+
b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);
93+
b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);
94+
95+
// 打印二叉树
96+
b.toString(b.root);
97+
System.out.println();
98+
99+
// 是否存在节点值10
100+
TreeNode node01 = b.search(10);
101+
System.out.println("是否存在节点值为10 => " + node01.value);
102+
// 是否存在节点值11
103+
TreeNode node02 = b.search(11);
104+
System.out.println("是否存在节点值为11 => " + node02);
105+
106+
// 删除节点8
107+
TreeNode node03 = b.delete(8);
108+
System.out.println("删除节点8 => " + node03.value);
109+
b.toString(b.root);
110+
111+
112+
}
113+
}

0 commit comments

Comments
 (0)