java-binary search tree finden Eltern

im arbeiten auf eine Methode zu finden, die Eltern der anode. Ich starte an der Wurzel und dann nach unten gehen die Blätter, solange Sie nicht null sind und nicht die Knoten des Kindes.

unten ist mein code, es ist ein wenig chaotisch, weil im Versuch zu testen, um zu sehen, was falsch läuft.

Den Baum, den ich habe, ist

Dem x übergeben wird in 20 so 10 die Eltern, aber wenn ich es laufen 22 kommt als der Elternteil. die while-Schleife scheint nicht zu arbeiten, ist es so, wie ich es geschrieben?

public Node<E> findParent(E x)
{
Node<E> node = root;

System.out.println("node is " + node.getData() + " before the search");
System.out.println("The value of x is " + x);
System.out.println("The value of node.getRight is " + node.getRight().getData());
boolean test = !node.getRight().getData().equals(x);
System.out.println("does nodes data equal x " + test);
while(((node!=null) && (node.getLeft()!=null) && (!node.getLeft().getData().equals(x))) || 
 ((node != null) && (node.getRight()!=null) && (!node.getRight().getData().equals(x))))
{ System.out.println("why didnt it stop");
    if(x.compareTo(node.getData()) < 0)
    {
        node = node.getLeft();
    }
    else
    {
        node = node.getRight();
    }
}
 System.out.println("node is " + node.getData() + " after the search");
return node;
}

Leute zu Fragen, zu erkennen Fehler in Ihrem code ist nicht besonders produktiv. Verwenden Sie den debugger (oder print-Anweisungen) zu verfolgen, das Verhalten Ihres Codes, und identifizieren Sie den Punkt, an dem Ihr Verhalten abweicht von dem, was Sie erwartet.
ich habe verfolgt das Verhalten von meinem code. das ist das, was alle print-Anweisungen sind, werde ich verfolgen, was der Wert von node am Anfang und am Ende. und ich machte Sie sicher, dass, wenn ich in 10, dann 20 ist das Rechte Kind. Ich glaube nicht, ich sollte haben gewesen markiert für diese Frage, ive verbrachte eine Menge Zeit bei der Ausführung durch, um zu sehen, wenn ich es richtig machen
Sollten Sie weiterhin mit diesem debugging-Ansatz. An einem gewissen Punkt, wird der Wert der einen Variablen wird nicht das sein, was Sie erwartet. An diesem Punkt, Sie haben gefunden Ihre Fehler.
und ich weiß, wenn es abweicht von dem, was ich erwarten, seine, wenn es in die while-Schleife, so vermute ich, dass etwas falsch ist mit den while-Schleifen Bedingungen
Ok, in diesem Fall sollten Sie bestimmen den Wert der einzelnen Komponenten der while-Bedingung. Ist jede das, was Sie erwartet/gedacht?
ja getestet habe ich jede Bedingung und Sie sind alle, was ich erwartet hatte. unten ist die Ausdrucke von meinem test. wie Sie sehen können die Knoten 10, also sollte es nicht gehen, in der während weil 10 20 Eltern werden.Knoten ist 10 vor der Suche Den Wert von x ist 20 Der Wert des Knotens.getRight ist 20 Knoten Daten gleich x ist "false" Knoten null ist? false-Knoten.getleft null? false-Knoten.getright null? false bedeutet Knoten.getleft gleich x? false bedeutet Knoten.getright gleich x? true
In diesem Fall haben Sie einen logischen Fehler bei der Gestaltung Ihres Codes. Wenn der code, der sich schlecht benimmt, dann ist mindestens eine dieser Bedingungen ist falsch. Die Aufgabe ist, herauszufinden, was man 😉
ich weiß, dass ich haben, um herauszufinden, was ist falsch, das ist, warum im Fragen fo rhelp
Ich kann Ihnen nicht mehr helfen, ohne Sie tatsächlich tun Sie Ihre debugging-für Sie. Sie müssen herausfinden (vielleicht mit Bleistift und Papier, Schritt für Schritt), was die Logik sein sollte, und vergleichen diese zu dem, was du geschrieben hast in deinem code.

InformationsquelleAutor alexthefourth | 2013-03-02

6

Ich würde es anders machen: Mach die Rekursion in eine Hilfs-Methode übergeben wird der aktuelle Knoten und die aktuelle parent-node. Es macht alles viel einfacher:
```
public Node<E> findParent(E x) {
    return findParent(x, root, null);
}

public Node<E> findParent(E x, Node<E> node, Node<E> parent)
{
    if (node == null) {
        return null;
    } else if (!node.getData().equals(x)) {
        parent = findParent(x, node.getLeft(), node);
        if (parent == null) {
            parent = findParent(x, node.getRight(), node);
        }
    }
    return parent;
}
```
- so parent == null bestimmt, ob Sie Links oder rechts auf dem Baum?
- Nach der Feststellung, dass x ist der Knoten, an node diese immer Links geht, ersten. Wenn parent == null nach, dann x war nicht in den linken Teilbaum, und Sie müssen die Suche in den rechten Teilbaum.
- Äh, das war ja auch "Nach der Feststellung, dass x ist nicht bei node. ..."
InformationsquelleAutor Ted Hopp

private static void myparent(int data, Node R) 
{
    if( (R.left!=null && R.left.data == data) || (R.right!=null) &&(R.right.data == data) )
    {
        pRoot = R;
        return;
    }
    if (R.data <= data)
        myparent(data, R.right);
    else
        myparent(data, R.left);
}

Wo die "Daten" der Wert des Knotens ab, dessen übergeordnetes müssen wir suchen, und R ist der root-Knoten des BST.
pRoot ist meine Globale Datenstruktur, wie ich es bei anderen Operationen auf BST.

InformationsquelleAutor JustVirtually

-1

Dies ist nur pseudocode. wenn Sie an einem Knoten x werden, überprüfen Sie die Schlüssel (des Kindes, dessen Eltern zu finden ist) in der linken und rechten Knoten. Wenn Sie übereinstimmen, dann sind Sie bereits auf der übergeordneten. Wenn nicht, dann ist es sicher zu bewegen in der Richtung des Elements, und führen Sie es erneut.

Beachten Sie, dass wir überprüfen in den nächsten level, bevor Sie fortfahren.
```
while(node!=null){

  if(node.left==key || node.right==key) return node;

  if(key<node.data) node=node.left;

  else node=node.right;

  return null;
}
```
InformationsquelleAutor Ayush Gupta

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.