Java-Member-Funktion für BST in der Reihenfolge Traversal

Question

Ich war kürzlich in einem Interview und wurde gebeten, eine Reihenfolge Traversal für eine BST mit der Java-Member-Funktion Prototyp unten zu codieren.

public void inOrderPrint() 

Ich war durch die Tatsache verwirrt, dass es irgendwelche Parameter nicht einnahm. Ich bin gewohnt, dass der Knoten übergeben wird. Es ist sehr einfach, den Baum mit dem übergebenen Knoten zu durchqueren ... Ich bin nur ein wenig verwirrt, wie man ohne die anfängliche Referenz darüber gehen würde?

Answer 1

Die angegebene Signatur ist sinnvoll, wenn inOrderPrint() in der Node Klasse der BST definiert ist, dann wird angenommen, dass der zu durchlaufende Baum derjenige ist, der im aktuellen Knoten verwurzelt ist. Alternativ könnte der Baum ein Attribut in der aktuellen Klasse sein. Unter der Annahme, dass das Verfahren in der Knotenklasse ist, würde es so etwas wie diese - und tut merken, wie die Rekursion aufgerufen wird:

public class Node { 

    private Node left; 
    private Node right; 
    private Object value; 

    public void inOrderPrint() { 
    if (left != null) 
     left.inOrderPrint(); 
    System.out.println(value); 
    if (right != null) 
     right.inOrderPrint(); 
    } 

} 

Answer 2

In Anbetracht, dass es eine Member-Funktion, kann man davon ausgehen, dass Sie Zugriff haben an die Wurzel (zB this.root). Sie könnten diese Methode einfach mit einer Methode überladen, bei der Sie einen Knoten übergeben. Sie würden dann die überladene Methode innerhalb der gegebenen mit der Wurzel aufrufen.

EDIT:

ich die Methode gedacht wurde, in dem Baum definiert ist, nicht in der Node-Klasse. Man könnte es so machen: (stellen Sie sicher, für null zu überprüfen!)

public void inOrderPrint(){ 
    //traverse down the left tree 
    this.left.inOrderPrint(); 
    System.out.println(this); 
    //traverse down the right tree  
    this.right.inOrderPrint(); 
}