Binärensuchbaum

[Waterman]

Hallo könnte mir jemand vielleicht einen Ansatz bzw. wie ich vorgehen könnte geben ?

Das ist die Aufgabe:

Ergänzen Sie die aus der Vorlesung bekannte Klasse IntSearchTree, die einen binären Suchbaum realisiert. Gehen
Sie bei der Implementierung der geforderten Methoden aber davon aus, dass Ihnen in der Klasse IntSearchTree
keine Methoden zur Verfügung stehen und Sie auch nur genau die geforderten Methoden hinzufügen dür-
fen. Änderungen und Ergänzungen außerhalb der jeweils geforderten Methode sind bei keiner Teilaufgabe
erlaubt. Beachten Sie, dass bei allen Methoden auch der leere Teilbaum als Parameter vorkommen kann.
Die Klasse Knoten finden Sie im Anhang.

a) Vervollständigen Sie die Methode IntNode copy(IntNode k).
Die Methode kopiere soll einen neuen Teilbaum zurückgeben, der eine exakte Kopie des Teilbaums mit
der Wurzel k darstellt. Der Teilbaum mit der Wurzel k und die erzeugte Kopie dürfen keine gemeinsamen
Objekte der Klasse IntNode besitzen.

public class IntNode {
    private int value;
    private IntNode leftChild, rightChild;
    public IntNode( int i ) {
        value = i; leftChild = rightChild = null;
    }
    public IntNode( int i, IntNode left, IntNode right ) {
        value = i; leftChild = left; rightChild = right;
    }
    public int getValue() { return value; }
    public void setValue(int i) { value = i; }
    public IntNode getLeftChild() { return leftChild; }
    public IntNode getRightChild() { return rightChild; }
    public void setLeftChild( IntNode node ) { leftChild = node; }
    public void setRightChild( IntNode node ) { rightChild = node; }
    public boolean isLeaf() { 
        return leftChild == null && rightChild == null;
    }
}

public class IntSearchTree{
        private IntNode root;
        private int size;
       
        public IntNode copy(IntNode k){

        }
}
}

 

[DrZoidberg]

Ich vermute mal das soll so aussehen

public IntNode copy(IntNode k){
    if(k == null) return null;
    else return new IntNode(k.getValue(), copy(k.getLeftChild()), copy(k.getLeftChild()));
}

Komisch ist allerdings, dass IntNode nicht als static declariert ist. Sollte es eigentlich sein.

 

[Waterman]

Danke für deine schnelle Antwort .
Ich hätte da noch eine andere Aufgabe bei der ich Hilfe gebrauchen könnte.

Aufgabe:

Vervollständigen Sie die Methode nPfad(IntNode k, int n).
Die Methode nPfad soll true zurückgeben, falls es mindestens einen Pfad vom Knoten k zu einem
Blatt gibt, auf dem genau n Knoten auftreten, die jeweils genau zwei Nachfolgeknoten(damit sind 2 Kinder gemeint) besitzen; sonst soll
false zurückgegeben werden. Dabei gehört der Knoten k mit zu dem Pfad.
Für einen leeren Pfad wird immer false zurückgegeben.
Beispiel:
Die vier Pfade von k zu den Blättern enthalten:
Pfad 20-14-15: 1 Knoten mit zwei Nachfolgern
Pfad 20-32-25-22: 3 Knoten mit zwei Nachfolgern
Pfad 20-32-25-26: 3 Knoten mit zwei Nachfolgern
Pfad 20-32-40-50: 2 Knoten mit zwei Nachfolgern

Wie sollte ich hier am besten vorgehen ?

 

[DrZoidberg]

Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe, aber ich denke so könnte es gehen.

public boolean nPfad(IntNode k, int n) {
    if(k == null || n < 0) return false;
    if(k.isLeaf()) return n == 0;
    IntNode right = k.getRightChild(), left = k.getLeftChild(); 
    if(left != null && right != null) n--;
    return nPfad(left,  n) || nPfad(right, n);
}

 

[Waterman]

Ich habe eine Testklasse implementiert und der Code funktioniert.
Du hast die Rekursion ja drauf, wenn du Lust und Zeit hast könntest du dir ja villeicht einmal ein anderes Problem von mir anschauen bei dem es auch um Rekursion geht (http://www.java-forum.org/java-basics-anfaenger-themen/154726-exception.html#post991258).

Vielen Dank für deine Hilfe

 

[Waterman]

Hallo ich habe gerade versucht eine Methode zu implementieren die alle Blätter eines Bsb. zu löschen und die anschließend eine Referenz auf die Wurzel des geänderten Baums zurückgibt.
Aber irgendetwas funktioniert nicht.

    public void loescheBlaetter(){
        root=loescheBlaetter(root);
    }
    private IntNode loescheBlaetter(IntNode n){
        if(n!=null){
            if(n.isLeaf()){
                n=null;   
            }else{
                loescheBlaetter(n.getLeftChild());
                loescheBlaetter(n.getRightChild());
            }
        }
        return n;
    }

 

[DrZoidberg]

n ist eine lokale Variable. Wenn du die änderst, hat das keine Wirkung auf den Baum.

[Java]
private IntNode loescheBlaetter(IntNode n){
if(n!=null){
if(n.getLeftChild() != null && !n.getLeftChild().isLeaf()) {
loescheBlaetter(n.getLeftChild());
} else {
n.setLeftChild(null);
}
if(n.getRightChild() != null && !n.getRightChild().isLeaf()) {
loescheBlaetter(n.getRightChild());
} else {
n.setRightChild(null);
}
}
return n;
}
[/Java]