Java顺序遍历BST的成员函数

Question

我最近在接受采访时被要求使用下面的 java 成员函数原型为 BST 编写顺序遍历代码。

public void inOrderPrint()

我对它没有接受任何参数这一事实感到困惑。我习惯了要传入的节点。通过传入的节点遍历树非常容易......我只是有点困惑如果没有初始参考怎么办？

Answer 1

如果在 BST 的 Node class 中定义了 inOrderPrint()，那么给定的签名是有意义的，那么这意味着要遍历的树就是以当前节点为根的树.或者，树可能是当前 class 中的一个属性。假设该方法在节点 class 中，它会是这样的 - do 注意递归是如何被调用的：

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

鉴于它是一个成员函数，可以假设您可以访问根（例如 this.root）。您可以使用传入节点的方法重载此方法。然后，您将使用根调用给定方法中的重载方法。

编辑：

我认为该方法是在树中定义的，而不是在节点中定义的 class。您可以这样做：（确保检查是否为空！）

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

Java顺序遍历BST的成员函数

Java member function for BST in order traversal

java

function

member