java - 二叉搜索树的非递归底层方法

Question

我一直在努力让它工作，但虽然它适用于大多数输入，但有时它会给出错误的输出。我花了一些时间调试代码，似乎问题是当我得到一个小于根但大于根下的左节点的节点时。

如果右子树中没有节点是该键的地板节点，如何遍历右子树并仍然返回正确的键？

Answer 1

回想一下，如果您以递归方式执行任何操作，它都可以转换*为迭代。

让我们考虑取结构良好的 BST 的 floor，它应该只是小于或等于树中键的最小元素。我们所要做的就是遍历树来获取它。

让我们递归地实现它，这样我们就可以梳理出迭代和递归之间的一些重要推论。

// Assuming non-null root node with method declaration
private Node floor(Node root, Key key, Node lowestNode) {
    if(key.compareTo(root.getKey()) <= 0) {
        if(root.getLeft() != null) {
            return floor(root.getLeft(), key, lowestNode);
        } else {
            return root.compareTo(lowestNode) < 0 ? root : lowestNode;
        }
     } else {
        if(root.getRight() != null) {
           lowestRightNode.add(root);
           return floor(root.getRight(), key, lowestNode);
        } else {
           return lowestNode;
     }
}

让我们来看看成功的条件。

• 如果我们比较一个节点小于或等于我们的键值:
  • 如果我们有一个左 child ，就会有更小的东西。遍历树的左半部分。
  • 否则，我们在地板上——这意味着我们在值小于或等于我们的键的节点上。归还它。
• 否则(我们的节点的值大于我们的键):
  • 如果我们有一个合适的 child ，我们的工作可能还没有完成(一些更小的事情)。我们希望保留它，因为我们可以离开树，所以让我们存储它，然后向下遍历树的右半部分。
  • 否则，我们就从树上掉下来了。返回我们跟踪的最小元素。

一个例子可能看起来像这样:

        9
       / \
      3  14
     / \  
    1  2

key 为 12:

• 与 9 相比。我们更大。将 9 存储在我们的最低节点变量中，向右递归。
• 与 14 比较。我们更小，但我们没有左 child 。我们将值 14 与 9 进行比较，并且 9 较小，因此我们返回带有 9 的节点。

如果我们想将其转换为迭代，请考虑您的起点、条件检查和增量步骤。

• 起点:一个非空节点
• 条件检查:
  • key.compareTo(root.getKey()) <= 0
    • root.getLeft() != null
      • 继续
    • root.compareTo(lowestRightNode) < 0 ? root : lowestRightNode
      • 终端
  • 其他
    • root.getRight() != null
      • 存储临时值并继续
    • return lowestRightNode
      • 终端

密切关注您的延续条件，以及您必须做哪些其他工作来跟踪您目前看到的最低节点(仅适用于右侧)。

^{*:当然，某些递归操作的转换痛苦比其他操作要多。}