Hi,
ich komme grad nicht weiter und hoffe Ihr könnt mir helfen
Ich möchte Knoten aus einem Baum löschen, dazu muss ich ja zuerst den gewünschten Knoten im Baum suchen. Da ist jedoch schon mein erstes Problem, ich kreige es nicht hin, aber bin der Meinung das man es rekursiv machen kann...
Hier ist mein Code:
Danke für Eure Hilfe
ich komme grad nicht weiter und hoffe Ihr könnt mir helfen
Ich möchte Knoten aus einem Baum löschen, dazu muss ich ja zuerst den gewünschten Knoten im Baum suchen. Da ist jedoch schon mein erstes Problem, ich kreige es nicht hin, aber bin der Meinung das man es rekursiv machen kann...
Hier ist mein Code:
Danke für Eure Hilfe
Java:
package aufgabe2;
import java.util.LinkedList;
import de.tu.tree.Tree;
public class BinarySearchTree implements Tree<Integer> {
protected BinTreeNode root;
protected int size = 0;
private boolean dataAlreadyExisted; //Gibt an, ob es den einzufügenden Wert im Baum bereits gibt.
public BinarySearchTree() {
this.root = null;
}
public BinarySearchTree(BinTreeNode n) {
root = n;
}
public boolean insert(Integer data) {
if (data != null) { //Kann nur einfügen, wenn auch ein gültiger Wert übergeben wird.
this.dataAlreadyExisted = false; //Den Wert gibt es bisher noch nicht.
this.root = insert(data, this.root); //Rufe die zweite insert-Methode auf, um den Wert einzufügen.
return this.dataAlreadyExisted; //Gebe zurück, ob der Wert existiert oder nicht.
}
return false; //Gebe false zurück, falls der Wert null ist.
}
private BinTreeNode insert(Integer data, BinTreeNode root) {
if (root == null) { //Einfügen in einem Blatt oder wenn der Baum leer ist. Wurzel des Teilbaums ist null, wenn Blatt oder Baum leer.
this.size++; //Erhöhe den Wert um 1.
return new BinTreeNode(data); //Erstelle den neuen Baum.
} else { //Wir sind noch an keinem Blatt angekommen und suchen weiter!
if (data.compareTo(root.getData()) < 0) { //Wir suchen im linken Teilbaum weiter, da der neue Wert kleiner als die Wurzel ist.
root.setLeft(insert(data, root.getLeft())); //Rufe rekursiv insert wieder auf für den neuen Teilbaum und setze dann den linken Teilbaum neu!
} else if (data.compareTo(root.getData()) > 0) { //Wert ist größer als die Wurzel also suchen wir im rechten Teilbaum weiter.
root.setRight(insert(data, root.getRight())); //Rufe rekursive insert wieder auf für den neuen Teilbaum und setze dann den rechten Teilbaum neu.
} else { //Den Wert gibt es schon im Baum.
this.dataAlreadyExisted = true; //Gebe den Baum einfach zurück und setze Boolean auf true.
}
return root;
}
}
public boolean remove(Integer i) {
if(root == null || i == null){
return false;
}
else if(i.compareTo(root.getData()) < 0) { // Wir suchen im linken Teilbaum, da der Wert kleiner als die Wurzel ist.
root.setLeft(remove(i)); //PROBLEM!!! suchen im linken Teilbaum
}
else if (i.compareTo(root.getData()) > 0) { // Wert ist größer als die Wurzel also suchen wir im rechten Teilbaum weiter.
//??? //PROBLEM!!! Rufe rekursiv insert wieder auf für den neuen Teilbaum und setze dann den rechten Teilbaum neu!
}
if(root.isLeaf()) { // kein Nachfolger; Fall 1
root = null; // gefundenen Knoten einfach vernichten
size--;
return true;
}
else if (root.right.isLeaf() || root.left.isLeaf()){ // Ein Nachfolger; Fall 2
if (root.right == null){ // Falls der rechte Zweig "leer" ist
root = root.left; // Der alte Knoten wird durch den linken Zweig ersetzt
size--;
}
else if (root.left == null){ // Falls der linke Zweig "leer" ist
root = root.right; // Der alte Knoten wird durch den rechten Zweig ersetzt
size--;
}
else if (root.right != null && root.left != null){ // Zwei Nachfolger; Fall 3
}
}
else
return false;
}
}
Java:
package aufgabe2;
import de.tu.tree.BinNode;
public class BinTreeNode implements BinNode<Integer> {
Integer data;
BinTreeNode left;
BinTreeNode right;
public BinTreeNode(Integer data) {
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public BinTreeNode getLeft() {
return left;
}
public void setLeft(BinTreeNode left) {
this.left = left;
}
public BinTreeNode getRight() {
return right;
}
public void setRight(BinTreeNode right) {
this.right = right;
}
public boolean isLeaf() {
return right == null && left == null;
}
public String toString(){
return data.toString();
}
}