在二叉搜索树中查找重复条目的策略
我有一个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));
这意味着重复将被添加到他们的重复权利..对吗？
你展示的树假定（至少我假设...... ;-)）比左边的要少，而且比右边的要大，对吗？
所以你应该考虑两件事情：
你的树错了！ “10”头右侧的第二个“8”不能在那里，因为它小于10.正确的插入和正确的平衡将在“下一个”迭代中放入非常接近的位置从“左8”开始。
通过在左侧定义树为“小于或等于”，并在右侧定义“大于”，您将得到想要的结果：所有“8”将被链接在彼此的左侧一个简单的插入树。
递归算法可以快速解决这个问题。 您不必在整个树上递归，因为您可以使用BST的结构来搜索所需的值。
你所画的不是严格意义上的BST，我可能是错误的，但我相信它已经非常糟糕 - 左侧树中的所有数字都应该小于10，反之亦然。
链接地址: http://www.djcxy.com/p/55409.html上一篇: Strategy to find duplicate entries in a binary search tree