forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryTreeSort.java
More file actions
96 lines (70 loc) · 1.87 KB
/
Copy pathBinaryTreeSort.java
File metadata and controls
96 lines (70 loc) · 1.87 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
package Sorts;
import static Sorts.SortUtils.less;
import static Sorts.SortUtils.print;
/**
*
* @author Podshivalov Nikita (https://github.com/nikitap492)
*
* @see SortAlgorithm
*
*/
public class BinaryTreeSort implements SortAlgorithm {
interface TreeVisitor<T extends Comparable<T>> {
void visit(Node<T> node);
}
private static class SortVisitor<T extends Comparable<T>> implements TreeVisitor<T> {
private final T[] array;
private int counter;
SortVisitor(T[] array) {
this.array = array;
}
@Override
public void visit(Node<T> node) {
array[counter++] = node.value;
}
}
private static class Node<T extends Comparable<T>>{
private T value;
private Node<T> left;
private Node<T> right;
Node(T value) {
this.value = value;
}
void insert(Node<T> node) {
if (less(node.value, value)){
if (left != null) left.insert(node);
else left = node;
}
else {
if (right != null) right.insert(node);
else right = node;
}
}
void traverse(TreeVisitor<T> visitor) {
if ( left != null)
left.traverse(visitor);
visitor.visit(this);
if ( right != null )
right.traverse(visitor );
}
}
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
Node<T> root = new Node<>(array[0]);
for (int i = 1; i < array.length; i++) {
root.insert(new Node<>(array[i]));
}
root.traverse(new SortVisitor<>(array));
return array;
}
public static void main(String args[]) {
Integer[] intArray = {12, 40, 9, 3, 19, 74, 7, 31, 23, 54, 26, 81, 12};
BinaryTreeSort treeSort = new BinaryTreeSort();
Integer[] sorted = treeSort.sort(intArray);
print(sorted);
Double[] decimalArray = {8.2, 1.5, 3.14159265, 9.3, 5.1, 4.8, 2.6};
print(treeSort.sort(decimalArray));
String[] stringArray = {"c", "a", "e", "b","d", "dd","da","zz", "AA", "aa","aB","Hb", "Z"};
print(treeSort.sort(stringArray));
}
}