Binäre Bäume
Gegeben ist ein Gerüst für Binärbäume mit int-Werten. Implementieren Sie folgende Funktionen:
- height(): Liefert die Höhe des Baums zurück (für einen Baum mit nur einem Knoten: 1, im Beispiel oben: 4).
- pathToMax(): Gibt den Pfad zum Maximum des Baums zurück. Im folgenden Beispiel (Maximum 20) sollte die Funktion ‘‘left->right’’ zurückgeben. Ist das Maximum die Wurzel, ist ein leerer String zurückzugeben.(Pfad von der Wurzel zum Maximum als String). Tip: Sie brauchen wahrscheinlich noch eine zweite Methode max(), die das Maximum selbst zurückliefert.
Hinweis: Die Methode isCompleteOrAlmostComplete() ist in einer späteren Aufgabe zu implementieren.
package de.hsrm.ads;
public class BinTree {
Node root;
static class Node {
Node left;
Node right;
int value;
Node(int value) {
this.value = value;
}
Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public BinTree() {
root = null;
}
public BinTree(Node root) {
this.root = root;
}
public int height() {
// FIXME
}
public String pathToMax() {
// FIXME
}
public boolean isCompleteOrAlmostComplete() {
// FIXME
}
public static void main(String[] args) {
}
}
Subato
