public class BinaryTree {
BinaryTreeNode top; // Wurzel des Binaeren Suchbaums
public BinaryTree() {
top = null;
}
/*
* BEGINN des zu implementierenden Bereichs
*/
/*
* Mit dieser Methode soll ein neuer Knoten mit der durch den Parameter
* number gegebenen Zahl in den Baum eingefuegt werden. Die vorhandene
* Struktur des Baumes soll dabei nicht geaendert werden und die neue Zahl
* als Blatt (Knoten ohne Nachfolger) im Baum zu finden sein. Ist die Zahl
* bereits im Baum vorhanden, soll nichts geschehen.
*
* Beispiel: 5 / \ 2 17 / / \ -3 8 20
*
* Aufruf von Tree.insert(4)
*
* 5 / \ 2 17 / \ / \ -3 4 8 20
*/
public void insert(int number) {
// oeffentliche Methode zum Aufrufen und behandeln der Sonderfaelle
// am Anfang, z.B. Behandlung des Verweises top
// Abfrage ist der Baum leer (top==null?)
if (top == null) {
// Baum leer und das Element mit number muss erzeugt werden
// und top darauf verweisen
top = new BinaryTreeNode(number);
} else {
insert(number, top);
}
}
private void insert(int number, BinaryTreeNode knoten) {
// Methode, die die meiste Arbeit erledigt
// betrachte den Knoten des BinaryTree knoten
// 1. Fall: number schon vorhanden -> fertig, nix tun und beenden
// 2. Fall: number ist kleiner als knoten.number
// -> links weiter machen, aber nur, wenn der Teilbaum links (smaller)
// nicht leer ist!
// sonst: neuen Knoten mit number als Inhalt links anfuegen
// 3. Fall: number ist groesser als knoten.number dann analog mit
// rechtem Teilbaum (larger)
// Algorithmus stellt insgesamt sicher, dass immer gilt knoten !=null
// !!!
if (number == knoten.number) {
// 1. Fall -> tu nix & beenden
return;
} else {
// 2. Fall oder 3. Fall
if (number < knoten.number) {
// also 2. Fall
if (knoten.smaller != null) {
// linker Teilbaum (smaller) ist nicht leer und dann dort
// rekursiv weiter machen
insert(number, knoten.smaller);
} else {
// 2. Fall und linker Teilbaum ist leer(smaller == null)
// dann einfuege-Stelle gefunden und neuen Knoten erzeugen
knoten.smaller = new BinaryTreeNode(number);
}
} else {
// hier also mit Sicherheit 3. Fall: number > knoten.number
if (knoten.larger != null) {
// rechter Teilbaum(larger) ist nicht leer und dann dort
// rekursiv weiter machen
insert(number, knoten.larger);
} else {
// 3. Fall und rechter Teilbaum (larger) == null
knoten.larger = new BinaryTreeNode(number);
}
}
}
}
/*
* Diese Methode soll die maximale Tiefe eines Baumes zurueckgeben. Die
* maximale Tiefe ist die Laenge des weitesten Weges den man von der Wurzel
* des Baumes zu einem Blatt zuruecklegen kann.
*
* Beispiel: 5 / \ 2 17 / -3
*
* Die maximale Tiefe wird in diesem Baum entlang des Pfades 5 -> 2 -> -3
* erreicht. Der Wert betraegt 3. Falls der Baum kein Element enthaelt und
* damit leer ist, soll die zurueckgegebene Tiefe 0 sein.
*/
public int maxDepth() {
if (top == null) { // der leere Baum hat die Tiefe 0
return 0;
} else {
return maxDepth(top);
}
}
private int maxDepth(BinaryTreeNode knoten) {
if (knoten == null) { // der leere Teilbaum hat die Tiefe 0
return 0;
} else { // Maximum der Tiefe der linken und rechten Teilbaeume +1 ist
// die
// Tiefe dieses Teilbaums
// besorge die Tiefe des linken Teilbaums
int linketiefe = maxDepth(knoten.smaller);
// besorge die Tiefe des rechten Teilbaums
// nun berechne das (Maximum der Tiefe von links und rechts) +1
int rechtetiefe = maxDepth(knoten.larger);
if (linketiefe < rechtetiefe) {
return rechtetiefe + 1;
} else {
return linketiefe + 1;
}
}
}
public int nodeCount() {
// 1. Fall ist der Baum leer?
if (top == null) {
return 0;
} else {
return nodeCount(top);
}
}
private int nodeCount(BinaryTreeNode knoten) {
// hole die Anzahl des linken Teilbaums
// hole die Anzahl des rechten Teilbaums
// 0addieren plus 1 und zurueckgeben
if (knoten == null) {
return 0;
} else {
return nodeCount(knoten.smaller) + nodeCount(knoten.larger) + 1;
}
}
private int sumOfElements() {
if (top == null) {
return 0;
} else {
return sumOfElements(top);
}
}
public int sumOfElements(BinaryTreeNode node) {
if (node == null) {
return 0;
}
int summe = 0;
summe = sumOfElements(node.getSmaller())
+ sumOfElements(node.getLarger()) + node.getNumber();
return summe;
}
public void setMaximum(){
setMaximum(top.getNumber(), top);
}
private void setMaximum(int number, BinaryTreeNode node){
if(node==null){
return;
}
setMaximum(node.getNumber(), node.getSmaller());
setMaximum(node.getNumber(), node.getLarger());
if(node.number<number)
node.number=number;
//setMaximum(node.getNumber(), node.getSmaller());
//setMaximum(node.getNumber(), node.getLarger());
}
public void printBT() {
printBT(0, top);
}
private void printBT(int indent, BinaryTreeNode kn) {
if (kn != null) { // linken Teilbaum ausgeben
printBT(indent + 1, kn.smaller);
// nun den Knoten ausgeben, um indent Blank-Zeichen einruecken
for (int i = 0; i < indent; i++) {
System.out.print(" ");
}
System.out.println(kn.number);
// nun den rechten Teilbaum ausgeben
printBT(indent + 1, kn.larger);
}
}
/*
* ENDE des zu implementierenden Bereichs
*/
public static void main(String[] args) {
// int [] numbers = {10, 30, 5,-3, 7,15,11,17,99};
BinaryTree derBaum = new BinaryTree();
derBaum.insert(10);
derBaum.insert(30);
derBaum.insert(5);
derBaum.insert(-3);
derBaum.insert(7);
//derBaum.insert(15);
//derBaum.insert(11);
//derBaum.insert(17);
//derBaum.insert(99);
derBaum.setMaximum();
derBaum.printBT();
System.out.println("der Baum enthaelt " + derBaum.nodeCount()
+ " Knoten und ist so tief:" + derBaum.maxDepth());
}}
