二叉搜索树- lower()方法实现

Question

我试图实现一个E lower(E e)方法到BST(二叉搜索树)数据结构。它应该是这样工作的——(返回集合中最大的元素，严格小于给定的元素，如果没有这样的元素，则返回null)。我被这个问题难住了。任何建议吗?

例如，如果我有一个二叉树:调用方法lower(6)，应该返回5

5/
16

我的代码示例(Java)

public E lower(E e)
{
if (e== null) {
throw new IllegalArgumentException("Element is null in lower(E element)");
}
BstNode<E> node = root;
BstNode<E> parent = null;
BstNode<E> ch = null;
int cmp = c.compare(e, root.element);
while(node != null)
{
if (cmp > 0)
{
if(node.right != null)
{
node = node.right;
}
else
return node.element;
}
else
{
if(node.left != null)
{
node = node.left;
}
else
///DONT KNOW WHAT TO DO HERE
}
}
return null;
}

Answer 1

如果我理解正确的话，您需要找到小于输入的最大元素。

。如果你的树是:

5
/   
3     8
/    /
2   4 6

7

您希望输入的lower(8)返回7。

可以通过顺序遍历来实现。这将允许您按照元素的排序顺序遍历二叉树。然后可以使用它来返回输入之前的元素。一种方法是将按顺序遍历存储在数组中，然后在输入位置之前打印元素1的索引。如果不存在这样的元素，这也允许您返回NULL。

您可以在这里找到将顺序遍历存储到数组中的实现。

Answer 2

您可以迭代BT并存储小于输入的最大的数字。您还可以通过不搜索根值大于您的值或小于当前最大值(小于输入值)的子树来提高效率。

Answer 3

算法:

1. 让当前节点为根节点
2. 重复:
   • 如果当前节点大于或等于e并且有左子节点，则向左移动。
   • 如果当前节点小于e并且有右子节点，则向右移动。
   • 如果上面没有产生移动，那么停止循环

,

• 如果结果节点严格小于e，则它是想要的结果。否则,
• 如果结果节点恰好是e，不是根节点，并且大于它的父节点，那么它的父节点就是想要的结果。否则
• 树中没有低于e的节点。