从递归方法编写迭代方法

Question

我正在做二叉搜索树作业，我被要求将递归方法转换为迭代方法。这是递归方法，下面是我的迭代方法。此方法应该 return 包含第 k 个键的节点。我的方法一直给我一个 NullPointerException，我不确定为什么。谢谢你。

提供的代码：

public Key select(int k) {
    Node node = select(root, k);
    if (node==null) {
        return null;
    } else {
        return node.key;
    }
}

// Return Node containing kth key (zero based)
private Node select(Node node, int k) { 
    if (node == null) return null;

    int t = size(node.left);
    if (t > k)
        return select(node.left, k);
    else if (t < k)
        return select(node.right, k - t - 1);
    else
        return node;
}

我的代码：

public Key selectI(int k) {
    return selectI(root, k);
}

private Key selectI(Node node, int k) {
    Node curr = node;
    while (curr != null) {
          int t = size(node.left);
          if (t > k) {
               curr = node.left;
          } else if (t < k) {
               curr = node.right;
               k = (k - (t - 1));

          } else
               return curr.key;
    }
    return null;
}

Answer 1

问题似乎是您没有更新 k 的值。这通常是递归完成的，但如果你要制作一个迭代函数，你必须用数学方法来完成。当您向左传递 (t > k) 时，您继续搜索大小为 k 的节点。当您向右传递 (t < k) 时，您正在搜索大小为 k = (k - (t - 1)) 的节点。最终 t 和 k 将等于或为零，在这种情况下，您已经找到了要查找的节点！

还要确保您不断更新正在查看的当前节点的大小。你不想只看树的大小，这会破坏你的 t 和 k 值之间的数学关系，这将导致程序运行直到没有更多的节点可看！

从递归方法编写迭代方法

Writing iterative method from recursive method

recursion

binary-search-tree