地板实现在二叉查找树

Question

考虑一下Robert Sedgewick在他的网站上的声明：

我非常困惑，当键大于根时会发生什么，尤其是当他说：“但只有当右子树中有一个键小于或等于键时”。我想他的意思是，如果键小于根，那么键肯定在左子树中。另一方面，如果密钥更大，则密钥“可能”在正确的子树中，因此也可能在正确的子树上找不到密钥。根据他的floor（）方法：

public Key floor(Key key)
{
   Node x = floor(root, key);
   if (x == null) return null;
   return x.key;
}

private Node floor(Node x, Key key)
{
   if (x == null) return null;
   int cmp = key.compareTo(x.key);
   if (cmp == 0) return x;
   if (cmp < 0)  return floor(x.left, key);
   Node t = floor(x.right, key);
   if (t != null) return t;
   else           return x;
}

他确实检查了右子树，但没有检查左子树。但我完全不能想出一个例子，其中键大于根，但小于右子树中的键。我真的认为这是不可能的。我错过了一些东西。有人能解释我遗漏了什么吗？

Answer 1

一个简单的解决方案：

            int FloorInBST(Node* root,int data)
            {
              if(root == NULL)
              {
                  return -1;//when MinNode of tree is greater than the input value
              }
              if(root->data == data) return data;

              if(root->data > data)
              {
                  return FloorInBST(root->left, data);//MUST be in left subtree 
              }
              else if (root->data < data)
              {
                  //MAY be in right subtree OR root itself
                  int floor = FloorInBST(root->right, data);
                  return (root->data >= floor ? root->data:floor);
              }
            }

Answer 2

如果你有一棵树喜欢（原谅我的ASCII艺术技巧）

  3
 / \
1   5

那么你要找的是第（4）层

1. 搜索键大于root
2. 右子树中没有比搜索键小的键，因此
3. 结果是根键（3）