Hallo,
ich habe eine Frage, wie müsste das BinTree in der mainmethode aussehen?
So wie es jetzt ist, ist es irgendwie verkehrt
Ich hoffe, mir kann jem. helfen.
Müsste das vielleicht BinTree<E> oder so heißen?
Vielen Dank.
ich habe eine Frage, wie müsste das BinTree in der mainmethode aussehen?
So wie es jetzt ist, ist es irgendwie verkehrt
Code:
public interface BinTree<E> {
E root();
BinTree<E> left();
BinTree<E> right();
/**
* @return
*/
Comparable value();
public int height();
}
Code:
public class CheckAVL implements BinTree {
/** Füllt ein Stack aufsteigend geordnet mit den Werten aus dem Baum */
private Stack TraverseTree(BinTree btree, Stack s) {
if(btree != null) {
if(btree.left() != null) s.concat(TraverseTree(btree.left(), s));
s.push(btree.value());
if(btree.right() != null) s.concat(TraverseTree(btree.right(), s));
return s;
}
return null;
}
/** Prüft, ob der Baum ein Suchbaum ist. */
public boolean CheckSuchBaum(BinTree btree) {
Stack s = TraverseTree(btree, new Stack());
boolean erg = true;
Comparable val = s.pop();
while(!s.isEmpty()) {
Comparable tmp = s.pop();
erg = erg && (tmp.compareTo(val) < 0);
val = tmp;
}
return erg;
}
/** Prüft, ob der Baum ausgeglichen ist. */
public boolean CheckAusgeglichen(BinTree btree) {
int lh, rh;
if(isLeaf()) return true;
lh = btree.left()==null?0:btree.left().height();
rh = btree.right()==null?0:btree.right().height();
if(Math.abs(lh - rh) <= 1) {
if(btree.left() != null && btree.right() != null)
return CheckAusgeglichen(btree.left()) && CheckAusgeglichen(btree.right());
if(btree.right() != null) return CheckAusgeglichen(btree.right());
else return CheckAusgeglichen(btree.left());
}
return false;
}
public boolean CheckInvAVL(BinTree btree) {
return CheckSuchBaum(btree) && CheckAusgeglichen(btree);
}
public Object root() {
return this;
}
public BinTree left(BinTree left) {
return left;
}
public BinTree right(BinTree right) {
return right;
}
public boolean isLeaf(BinTree left, BinTree right) {
return (isEmpty(left) && isEmpty(right));
}
public boolean isEmpty(BinTree b){
return (b==null);
}
public boolean isEmpty() { //cannot be applied to this
throw new UnsupportedOperationException();
}
public Comparable value(BinTree value) {
return value;
}
public boolean isLeaf() {
return (isEmpty(left) && isEmpty(right));
}
/** Gibt die Höhe des Baumes zurück */
public int height() {
int l, r;
if(isLeaf()) return 0;
l = isEmpty(left)? 0: left.height() + 1;
r = isEmpty(right)? 0: right.height() + 1;
return Math.max(l,r);
}
}
Code:
public class TestCheckAVL extends CheckAVL {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
BinTree not_ausgeglichen = new BinTree(new BinTree(new BinTree(new BinTree("2"),"3",new BinTree("4")),"5",null),"6",new BinTree("7"));
BinTree not_suchbaum = new BinTree(new BinTree("7"),"6",new BinTree("8"));
BinTree avl_baum = new BinTree(new BinTree(new BinTree("3"),"4",new BinTree("5")),"6",new BinTree(null,"7",new BinTree(null,"8",new BinTree("9"))));
CheckAVL avl = new CheckAVL();
System.out.println(avl.CheckInvAVL(not_ausgeglichen));
System.out.println(avl.CheckInvAVL(not_suchbaum));
System.out.println(avl.CheckInvAVL(avl_baum));
}
}
Ich hoffe, mir kann jem. helfen.
Müsste das vielleicht BinTree<E> oder so heißen?
Vielen Dank.