FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Trees/BinaryTree.java at master · eurafa/Java · GitHub
eurafa
/
Java
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DataStructures
/
Trees
/
BinaryTree.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
272 lines (245 loc) · 6.03 KB
Breadcrumbs
Java
/
DataStructures
/
Trees
/
BinaryTree.java
Copy path
File metadata and controls
272 lines (245 loc) · 6.03 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
/**
* This entire class is used to build a Binary Tree data structure.
* There is the Node Class and the Tree Class, both explained below.
*
* @author Unknown
*
*/
/**
* This class implements the nodes that will go on the Binary Tree.
* They consist of the data in them, the node to the left, the node
* to the right, and the parent from which they came from.
*
* @author Unknown
*
*/
class
Node
{
/** Data for the node */
public
int
data
;
/** The Node to the left of this one */
public
Node
left
;
/** The Node to the right of this one */
public
Node
right
;
/** The parent of this node */
public
Node
parent
;
/**
* Constructor of Node
*
* @param value Value to put in the node
*/
public
Node
(
int
value
){
data
=
value
;
left
=
null
;
right
=
null
;
parent
=
null
;
}
}
/**
* A binary tree is a data structure in which an element
* has two successors(children). The left child is usually
* smaller than the parent, and the right child is usually
* bigger.
*
* @author Unknown
*
*/
class
Tree
{
/** The root of the Binary Tree */
private
Node
root
;
/**
* Constructor
*/
public
Tree
(){
root
=
null
;
}
/**
* Method to find a Node with a certain value
*
* @param key Value being looked for
* @return The node if it finds it, otherwise returns the parent
*/
public
Node
find
(
int
key
) {
Node
current
=
root
;
while
(
current
!=
null
) {
if
(
key
<
current
.
data
) {
if
(
current
.
left
==
null
)
return
current
;
//The key isn't exist, returns the parent
current
=
current
.
left
;
}
else
if
(
key
>
current
.
data
) {
if
(
current
.
right
==
null
)
return
current
;
current
=
current
.
right
;
}
else
{
// If you find the value return it
return
current
;
}
}
return
null
;
}
/**
* Inserts certain value into the Binary Tree
*
* @param value Value to be inserted
*/
public
void
put
(
int
value
){
Node
newNode
=
new
Node
(
value
);
if
(
root
==
null
)
root
=
newNode
;
else
{
//This will return the soon to be parent of the value you're inserting
Node
parent
=
find
(
value
);
//This if/else assigns the new node to be either the left or right child of the parent
if
(
value
<
parent
.
data
){
parent
.
left
=
newNode
;
parent
.
left
.
parent
=
parent
;
return
;
}
else
{
parent
.
right
=
newNode
;
parent
.
right
.
parent
=
parent
;
return
;
}
}
}
/**
* Deletes a given value from the Binary Tree
*
* @param value Value to be deleted
* @return If the value was deleted
*/
public
boolean
remove
(
int
value
){
//temp is the node to be deleted
Node
temp
=
find
(
value
);
//If the value doesn't exist
if
(
temp
.
data
!=
value
)
return
false
;
//No children
if
(
temp
.
right
==
null
&&
temp
.
left
==
null
){
if
(
temp
==
root
)
root
=
null
;
//This if/else assigns the new node to be either the left or right child of the parent
else
if
(
temp
.
parent
.
data
<
temp
.
data
)
temp
.
parent
.
right
=
null
;
else
temp
.
parent
.
left
=
null
;
return
true
;
}
//Two children
else
if
(
temp
.
left
!=
null
&&
temp
.
right
!=
null
){
Node
successor
=
findSuccessor
(
temp
);
//The left tree of temp is made the left tree of the successor
successor
.
left
=
temp
.
left
;
successor
.
left
.
parent
=
successor
;
//If the successor has a right child, the child's grandparent is it's new parent
if
(
successor
.
right
!=
null
&&
successor
.
parent
!=
temp
){
successor
.
right
.
parent
=
successor
.
parent
;
successor
.
parent
.
left
=
successor
.
right
;
successor
.
right
=
temp
.
right
;
successor
.
right
.
parent
=
successor
;
}
if
(
temp
==
root
){
successor
.
parent
=
null
;
root
=
successor
;
return
true
;
}
//If you're not deleting the root
else
{
successor
.
parent
=
temp
.
parent
;
//This if/else assigns the new node to be either the left or right child of the parent
if
(
temp
.
parent
.
data
<
temp
.
data
)
temp
.
parent
.
right
=
successor
;
else
temp
.
parent
.
left
=
successor
;
return
true
;
}
}
//One child
else
{
//If it has a right child
if
(
temp
.
right
!=
null
){
if
(
temp
==
root
){
root
=
temp
.
right
;
return
true
;}
temp
.
right
.
parent
=
temp
.
parent
;
//Assigns temp to left or right child
if
(
temp
.
data
<
temp
.
parent
.
data
)
temp
.
parent
.
left
=
temp
.
right
;
else
temp
.
parent
.
right
=
temp
.
right
;
return
true
;
}
//If it has a left child
else
{
if
(
temp
==
root
){
root
=
temp
.
left
;
return
true
;}
temp
.
left
.
parent
=
temp
.
parent
;
//Assigns temp to left or right side
if
(
temp
.
data
<
temp
.
parent
.
data
)
temp
.
parent
.
left
=
temp
.
left
;
else
temp
.
parent
.
right
=
temp
.
left
;
return
true
;
}
}
}
/**
* This method finds the Successor to the Node given.
* Move right once and go left down the tree as far as you can
*
* @param n Node that you want to find the Successor of
* @return The Successor of the node
*/
public
Node
findSuccessor
(
Node
n
){
if
(
n
.
right
==
null
)
return
n
;
Node
current
=
n
.
right
;
Node
parent
=
n
.
right
;
while
(
current
!=
null
){
parent
=
current
;
current
=
current
.
left
;
}
return
parent
;
}
/**
* Returns the root of the Binary Tree
*
* @return the root of the Binary Tree
*/
public
Node
getRoot
(){
return
root
;
}
/**
* Prints leftChild - root - rightChild
*
* @param localRoot The local root of the binary tree
*/
public
void
inOrder
(
Node
localRoot
){
if
(
localRoot
!=
null
){
inOrder
(
localRoot
.
left
);
System
.
out
.
print
(
localRoot
.
data
+
" "
);
inOrder
(
localRoot
.
right
);
}
}
/**
* Prints root - leftChild - rightChild
*
* @param localRoot The local root of the binary tree
*/
public
void
preOrder
(
Node
localRoot
){
if
(
localRoot
!=
null
){
System
.
out
.
print
(
localRoot
.
data
+
" "
);
preOrder
(
localRoot
.
left
);
preOrder
(
localRoot
.
right
);
}
}
/**
* Prints rightChild - leftChild - root
*
* @param localRoot The local root of the binary tree
*/
public
void
postOrder
(
Node
localRoot
){
if
(
localRoot
!=
null
){
postOrder
(
localRoot
.
left
);
postOrder
(
localRoot
.
right
);
System
.
out
.
print
(
localRoot
.
data
+
" "
);
}
}
}
Back
|
FazBrowse Home
|
New Git URL