-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinaryTree.java
113 lines (102 loc) · 2.88 KB
/
BinaryTree.java
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
package de.niklas.exercise.collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
* <strong>Binärbaum</strong><br>
* Implementation eines Binärbaums
*
* @see "25_Datenstrukturen_Aufgaben-2.pdf"
* @author Niklas Buse
*/
public class BinaryTree<T extends Comparable<T>> {
private T value;
private BinaryTree<T> left;
private BinaryTree<T> right;
/**
* Funktion um zu prüfen, ob der Baum gefüllt ist
* @return Ob der Baum leer ist
*/
public boolean isEmpty() {
return this.value == null;
}
/**
* Gebe den Wert des aktuell betrachten Wurzel zurück
* @return Wert der angefragten Wurzel
*/
public T getValue() {
return this.value;
}
/**
* Gebe den linken Teilbaum zurück
* @return linker Teilbaum
*/
private BinaryTree<T> getLeft() {
if (this.left == null) {
this.left = new BinaryTree<>();
}
return this.left;
}
/**
* Gebe den rechten Teilbaum zurück
* @return rechter Teilbaum
*/
private BinaryTree<T> getRight() {
if (this.right == null) {
this.right = new BinaryTree<>();
}
return this.right;
}
/**
* Füge einen Wert in den Binärbaum hinzu, sodass seine Eigenschaften bestehen bleiben
* @param newValue Einzufügender Wert
* @return Ob das Einfügen funktioniert hat
*/
public boolean add(T newValue) {
if (this.isEmpty()) {
this.value = newValue;
}
else if (this.value.compareTo(newValue) == 0) {
return false;
}
else if (this.value.compareTo(newValue) > 0) {
return this.getLeft().add(newValue);
}
else if (this.value.compareTo(newValue) < 0) {
return this.getRight().add(newValue);
}
return true;
}
/**
* Startmethode zum Baum traversieren
* @return Liste mit sortierten Eintrögen des Baums
*/
public List<T> traverse(){
List<T> list = new LinkedList<>();
this.traverseRecursive(list);
return list;
}
/**
* Rekursive Preorder Traversierung für Binärbaum
*/
private void traverseRecursive(List<T> list) {
if (!this.getLeft().isEmpty()) {
this.left.traverseRecursive(list);
}
if (!this.isEmpty()) {
list.add(this.getValue());
}
if (!this.getRight().isEmpty()) {
this.right.traverseRecursive(list);
}
}
public static void main(String[] args) {
BinaryTree<Integer> tree = new BinaryTree<>();
for(int i = 0; i < 10; i++){
Integer randInt = new Random().nextInt(0, 20);
System.out.printf("%d %b\n" , randInt, tree.add(randInt));
}
List<Integer> list = tree.traverse();
System.out.println(list);
}
}