Depth-First-Suche in Binären Bäumen/Graphen in Java

Ich habe versucht, für eine Weile, bis dieser Graph verkleidet als ein Binärer Baum arbeiten. Derzeit verwende ich eine Funktion, die Pässe in die Wurzel-Knoten und die ID des Knotens, die ich Suche. Problem ist nur, dass je nachdem, wie ich es code, eine meiner Seiten kann nie bekommen vergangenen 3 Knoten lang. Ich bin sicher, ich bin nur nicht tun, die Rekursion korrekt. Ich habe fest auf das die ganze Nacht, und kann nicht diese. Ich habe versucht, auf der Suche nach anderen Graphen und Bäume, ohne Erfolg. Wir sind nicht mit eigentlichen Eckpunkten oder anderen graph-ähnliche Eigenschaften, aber ich kann nicht einfach if (x <root.getID()) dann root.Links, weil das nicht halten, da es immer noch ein "graph"

Hier meine nicht funktionierende such-Algorithmus, der aufhört zu arbeiten, auf der rechten Seite, wenn ich es ein paar Knoten lang. Besucht wird unter Verwendung der HashSet () - Klasse.

private Node dfs(Node x, int id)
{
    if (x==null) //base case. Runs into null link
       return null;
    if(visited.contains(x.getID())) //visited before
       return null;
    visited.add(x.getID()); //don't go below Node again
    if(id==x.getID())
      return x;
    Node rc = dfs(x.getRightChild(), id);
    Node lc = dfs(x.getLeftChild(), id);
    //recursive calls

  if (lc.getID()==id)
      return lc;
  if(rc.getID()==id)
      return rc;
  return null;
}

Ich habe einen funktionierenden code für den Druck aller vom Baum, aber ich kann es nicht mehr zu ändern, für den Schlüssel-Vergleich im obigen code.

private String dfsPrint(Node x) //pass in root at top level
                                //returns a String containing all ID's
{
   if (x==null) //base case. Runs into null link
       return "";
   if(visited.contains(x.getID())) //visited before
       return "";
   visited.add(x.getID()); //don't go below Node again
   String lc = dfsPrint(x.getLeftChild()); //recursive stuffs
   String rc = dfsPrint(x.getRightChild());
   return Integer.toString(x.getID()) + " " + lc + rc;
}

Danke für jede Hilfe.

Edit: ich nehme an, ich werde ergänzen, was ich Tue. Ich habe eine Funktion makeRight oder makeLeft, setzt sich in einen neuen Knoten, und dann einen vorhandenen Knoten legt, hat es seinen linken oder rechten Kind.
Hier ist, die. In ihm Suche, ist die öffentliche Methode ruft die private dfs.

  Node search(int id) //calls private dfsSearch() returns null or a ref to 
                    //a node with ID = id
{
  int ID = id;
  Node x= dfs(root, ID);
  return x;
}


void ML(int x, int y) //ML command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putLeft(temp);

}

void MR(int x, int y)//MR command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putRight(temp);

}

Je nachdem, wie ich um die rekursiven Funktionen in if-Anweisungen für lc-und rc, eine andere Seite von dem Baum bekommt recursed zurück bis zu den Basis Fall, das ist, was mich vermuten das dfs-Methode ist, was falsch ist. Hier ist die angefragte Knoten-Klasse.

 class Node {
 private int ID; //ID of the Node. Distinct
 private Node leftChild;
 private Node rightChild;

 Node(int identification)//constructor

{
     ID = identification;
}
 Node(int identification, Node lt, Node rt) //constructor

{
 ID = identification;
 leftChild = lt;
 rightChild = rt;

}

int getID()

{
    return ID;
}

Node getLeftChild()
    {
           return leftChild;
    }
Node getRightChild()
{
    return rightChild;
}
void putLeft(Node lt)
{
    leftChild = lt;
}
void putRight (Node rt)
{
    rightChild = rt;
}

}

InformationsquelleAutor Scott | 2011-03-04