-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy pathBinaryTree.java
More file actions
106 lines (94 loc) · 2.72 KB
/
BinaryTree.java
File metadata and controls
106 lines (94 loc) · 2.72 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
Non-balanced binary tree:
- without outer container: nodes only.
- no repetitions
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BinaryTree {
private Integer value;
private BinaryTree left;
private BinaryTree right;
BinaryTree(Integer value) {
this.value = value;
this.left = null;
this.right = null;
}
public boolean insert(Integer value) {
if (value < this.value) {
if (this.left == null) {
this.left = new BinaryTree(value);
return true;
} else {
return this.left.insert(value);
}
} else if (value > this.value) {
if (this.right == null) {
this.right = new BinaryTree(value);
return true;
} else {
return this.right.insert(value);
}
} else {
return false;
}
}
public void inOrder(List<Integer> output) {
if (this.left != null)
this.left.inOrder(output);
output.add(this.value);
if (this.right != null)
this.right.inOrder(output);
}
public void preOrder(List<Integer> output) {
output.add(this.value);
if (this.left != null)
this.left.preOrder(output);
if (this.right != null)
this.right.preOrder(output);
}
public static void main(String[] args) {
List<Integer> expected, output;
BinaryTree t = new BinaryTree(0);
assert !t.insert(0);
assert t.insert(-2);
assert t.insert(-1);
assert t.insert(-3);
assert t.insert(2);
assert t.insert(1);
assert t.insert(3);
/* Insert. */
assert t.value == 0;
assert t.left.value == -2;
assert t.left.left.value == -3;
assert t.left.right.value == -1;
assert t.right.value == 2;
assert t.right.left.value == 1;
assert t.right.right.value == 3;
/* inOrder */
expected = new ArrayList<Integer>();
expected.add(-3);
expected.add(-2);
expected.add(-1);
expected.add(0);
expected.add(1);
expected.add(2);
expected.add(3);
output = new ArrayList<Integer>();
t.inOrder(output);
assert output.equals(expected);
/* preOrder */
expected = new ArrayList<Integer>();
expected.add(0);
expected.add(-2);
expected.add(-3);
expected.add(-1);
expected.add(2);
expected.add(1);
expected.add(3);
output = new ArrayList<Integer>();
t.preOrder(output);
assert output.equals(expected);
}
}