FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Trees/TreeTraversal.java at master · java66liu/Java · GitHub
java66liu
/
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
/
TreeTraversal.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
121 lines (109 loc) · 3.07 KB
Breadcrumbs
Java
/
DataStructures
/
Trees
/
TreeTraversal.java
Copy path
File metadata and controls
121 lines (109 loc) · 3.07 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
package
DataStructures
.
Trees
;
import
java
.
util
.
LinkedList
;
/**
* @author Varun Upadhyay (https://github.com/varunu28)
*/
// Driver Program
public
class
TreeTraversal
{
public
static
void
main
(
String
[]
args
) {
Node
tree
=
new
Node
(
5
);
tree
.
insert
(
3
);
tree
.
insert
(
2
);
tree
.
insert
(
7
);
tree
.
insert
(
4
);
tree
.
insert
(
6
);
tree
.
insert
(
8
);
// Prints 5 3 2 4 7 6 8
System
.
out
.
println
(
"Pre order traversal:"
);
tree
.
printPreOrder
();
System
.
out
.
println
();
// Prints 2 3 4 5 6 7 8
System
.
out
.
println
(
"In order traversal:"
);
tree
.
printInOrder
();
System
.
out
.
println
();
// Prints 2 4 3 6 8 7 5
System
.
out
.
println
(
"Post order traversal:"
);
tree
.
printPostOrder
();
System
.
out
.
println
();
// Prints 5 3 7 2 4 6 8
System
.
out
.
println
(
"Level order traversal:"
);
tree
.
printLevelOrder
();
System
.
out
.
println
();
}
}
/**
* The Node class which initializes a Node of a tree
* Consists of all 4 traversal methods: printInOrder, printPostOrder， printPreOrder & printLevelOrder
* printInOrder: LEFT -> ROOT -> RIGHT
* printPreOrder: ROOT -> LEFT -> RIGHT
* printPostOrder: LEFT -> RIGHT -> ROOT
* printLevelOrder: Prints by level (starting at root), from left to right.
*/
class
Node
{
Node
left
,
right
;
int
data
;
public
Node
(
int
data
) {
this
.
data
=
data
;
}
public
void
insert
(
int
value
) {
if
(
value
<
data
) {
if
(
left
==
null
) {
left
=
new
Node
(
value
);
}
else
{
left
.
insert
(
value
);
}
}
else
{
if
(
right
==
null
) {
right
=
new
Node
(
value
);
}
else
{
right
.
insert
(
value
);
}
}
}
public
void
printInOrder
() {
if
(
left
!=
null
) {
left
.
printInOrder
();
}
System
.
out
.
print
(
data
+
" "
);
if
(
right
!=
null
) {
right
.
printInOrder
();
}
}
public
void
printPreOrder
() {
System
.
out
.
print
(
data
+
" "
);
if
(
left
!=
null
) {
left
.
printPreOrder
();
}
if
(
right
!=
null
) {
right
.
printPreOrder
();
}
}
public
void
printPostOrder
() {
if
(
left
!=
null
) {
left
.
printPostOrder
();
}
if
(
right
!=
null
) {
right
.
printPostOrder
();
}
System
.
out
.
print
(
data
+
" "
);
}
/**
* O(n) time algorithm.
* Uses O(n) space to store nodes in a queue to aid in traversal.
*/
public
void
printLevelOrder
() {
LinkedList
<
Node
>
queue
=
new
LinkedList
<>();
queue
.
add
(
this
);
while
(
queue
.
size
() >
0
) {
Node
head
=
queue
.
remove
();
System
.
out
.
print
(
head
.
data
+
" "
);
// Add children of recently-printed node to queue, if they exist.
if
(
head
.
left
!=
null
) {
queue
.
add
(
head
.
left
);
}
if
(
head
.
right
!=
null
) {
queue
.
add
(
head
.
right
);
}
}
}
}
Back
|
FazBrowse Home
|
New Git URL