相关疑难解决方法(0)

我正在尝试找到二叉搜索树的定义,并且我一直在寻找不同的定义.

有人说,对于任何给定的子树,左子键小于或等于根.

有人说,对于任何给定的子树,右子键大于或等于根.

我的旧大学数据结构书中说"每个元素都有一个键,没有两个元素具有相同的键."

是否存在bst的通用定义？特别是关于如何处理具有相同密钥的多个实例的树.

编辑:也许我不清楚,我看到的定义是

1)左<= root <右

2)左<root <=右

3)左<root <右,这样就不存在重复的密钥.

我有一个BST,它有重复的条目.我想找到重复的条目.现在显然我可以编写一个遍历整个树的哑算法,这很容易.

但是,我想写一个更高效的.这是我到目前为止所做的/想到的:

假设以下树.

      10
     /   \
    5    15
   /\    / \
  2  8   10 16
      \    \
       8   12

如果我想找到所有8个,我将首先找到10的左边子树上的8个.要找到重复的,如果它没有正确的子节点,它将是右子树的最左边节点第一个父节点大于那个节点(8)？如果它确实有一个正确的子节点,那么它可以位于其右子树的最左侧节点,也可以位于其左侧子树的最右侧节点上？

那些是所有的情况,可以用一堆循环和if语句来实现吗？

如果没有,有什么更好的方法？有人可以帮忙吗？

谢谢

编辑:其实我刚刚意识到它不能是"最左边的节点"或"最右边的节点".这将找到下一个最高值或前一个最低值的节点.它之前是一个节点吗？

编辑2:

修复了我的BST示例.它遵循以下插入方法:

if (node == null) 
    return new NodeBST<Value>(name, value);

if (node.key().compareTo(name) > 0)
    node.setLeft(insert(node.left(), name, value));     
else
    node.setRight(insert(node.right(), name, value));

这意味着重复项将添加到重复项的右侧..对吗？