Vollständigkeitsprüfung für Bäume
Ergänzen Sie die Klasse BinTree um eine Methode isCompleteOrAlmostComplete(). Diese soll genau dann true zurückliefern wenn der Baum vollständig oder fast vollständig ist.
Hinweise:
- Um zu entscheiden ob ein Baum vollständig/fast vollständig ist, macht es Sinn die Vollständigkeit und die Höhe seiner beiden Teilbäume zu betrachten.
- Es hilft, zunächst auf Papier Fälle zu skizzieren, in denen Vollständigkeit bzw. Fast-Vollständigkeit vorliegt.
package de.hsrm.ads;
public class BinTreeCompleteness {
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 BinTreeCompleteness() {
root = null;
}
public BinTreeCompleteness(Node root) {
this.root = root;
}
public int height() {
// FIXME
}
public boolean isCompleteOrAlmostComplete() {
// FIXME
}
public static void main(String[] args) {
/*
* an incomplete sample tree
* (not fully complete, not almost complete)
*
* 1
* |_ 2
* |_ 4
* |_ 5
* |_ 7
* |_
*
* |_ 3
* |_
* |_ 6
*/
BinTreeCompleteness.Node n7 = new BinTreeCompleteness.Node(7);
BinTreeCompleteness.Node n6 = new BinTreeCompleteness.Node(6);
BinTreeCompleteness.Node n5 = new BinTreeCompleteness.Node(5, n7, null);
BinTreeCompleteness.Node n4 = new BinTreeCompleteness.Node(4);
BinTreeCompleteness.Node n3 = new BinTreeCompleteness.Node(3, null, n6);
BinTreeCompleteness.Node n2 = new BinTreeCompleteness.Node(2, n4, n5);
BinTreeCompleteness.Node n1 = new BinTreeCompleteness.Node(1, n2, n3);
BinTreeCompleteness tree = new BinTreeCompleteness(n1);
// should be false!
System.out.println(tree.isCompleteOrAlmostComplete());
}
}
Subato
