public class BSB{ private int value; private BSB left = null; private BSB right = null; private BSB root; /////////KONSTRUKTOREN////////// public BSB() { BSB(0, this); } public BSB(int i) { BSB(i, this); } //privater Kontruktor, um beim Einfügen neuer Knoten den Wurzelknoten übergeben zu können private BSB(int i, BSB root) { value = i; left = null; right = null; this.root = root; } //////////////////////////////// public BSB getLeft() { return left; } public BSB getRight() { return right; } public int getValue() { return value; } public BSB getRoot() { return root; } ///////////////////////////////////////////////////////////////////////////// //setLeft / Right: Ersetzen unter Erhalt der Ordnungseigenschaft public void insertTree(BSB b) { if(b.left != null) { root.insertTree(b.left); } if(b.right != null) { root.insertTree(b.right); } root.insert(b.value); } public void setLeft(BSB b) { left = null; root.insertTree(b); } public void setRight(BSB b) { right = null; root.insertTree(b); } //Einfügen des Wertes und entfernen des alten Knotens aus dem Baum public void setValue(int v) { if(this == this.root) { value = v; BSB tmpleft = this.left; BSB tmpright = this.right; left = null; right = null; insertTree(tmpleft); insertTree(tmpright); return; } //ab root durchlaufen und Knoten über dem aktuellen suchen; dazu wird der aktuelle Wert genutzt BSB parent = root; //solange der relevante Knoten nicht ein Unterast von parent ist while((parent.left != this) && (parent.right != this)) { if(this.value <= parent.value) { parent = parent.left; } else { parent = parent.right; } } //parent gefunden; Wert kann in aktuellen Knoten gesetzt werden this.value = v; //um Ordnungseigenschaft zu erhalten, wird der Unterknoten von parent entnommen und komplett wieder eingefügt //wenn der relevante Knoten der linke Unterknoten von parent ist if(parent.left == this) { parent.setLeft(this); } else if(parent.right == this) //...der rechte... { parent.setRight(this); } } public String toString() { String s = ""; if(left != null) s += left.toString() + ", "; s += value; if(right != null) s += ", "+ right.toString(); return s; } public boolean contains(int n) { if(value == n) return true; else if((n < value) && (left != null)) return left.contains(n); else if((n > value) && (right != null)) return right.contains(n); return false; } public void insert(int n) { if(n > value && right != null) right.insert(n); else if(n > value && right == null) { right = new BSB(n,root); } else if(n < value && left != null) left.insert(n); else if(n <= value && left == null) { left = new BSB(n,root); } //Wert der schon enthalten ist ein weiteres mal einfügen (wie in Angabe) else if(n == value && left != null) { BSB tmp = this.getLeft(); left = new BSB(n,root); left.left = tmp; } } public static void main(String[] args) { BSB baum = new BSB(50); BSB baum2 = new BSB(); baum2.insert(10); baum2.insert(20); baum2.insert(70); System.out.println("Baum1"); System.out.println(baum2); baum.insert(15); baum.insert(90); baum.insert(25); baum.insert(67); baum.insert(79); baum.insert(44); baum.insert(32); baum.insert(55); //wenn auskommentiert: manuelles eingeben der Elemente; /* System.out.println("10 Elemente eingeben"); java.util.Scanner in = new java.util.Scanner(System.in); for(int i = 0; i < 10; i++) // 10 Zahlen einlesen in baum { int x = in.nextInt(); baum.insert(x); } in.close(); */ System.out.println("Baum2"); System.out.println(baum); if(baum.contains(50)) System.out.println("Baum enthält 50"); else System.out.println("Baum enthält 50 nicht"); System.out.println("linker Teilbaum wird entfernt; erster Baum eingefügt"); baum.setLeft(baum2); System.out.println(baum); System.out.println("Wert des rechten Teilbaums auf 99"); System.out.println("Wert davor: " + baum.getRight().getValue()); baum.getRight().setValue(99); System.out.println(baum); System.out.println("SetValue(33) an Wurzel"); baum.setValue(33); System.out.println(baum); }}