处理二叉搜索树中的重复项的优雅方法是什么？我们假设每个键都有几个不同的关联值。我需要做的是按顺序迭代所有值。因此，如果我有 2 个带有键 1 的值 A 和 B，以及一个带有键 2 的值 C，那么当调用类似的方法时，我希望得到对:(1,A)、(1,B)、(2,C) TreeIterator.next();
我能想到:
- 每个节点都有一个键和一个值数组，具有相同键的值位于该数组中
- 每个节点都有一个
已访问标志
还有其他建议吗？作为一般准则，我希望 Tree 实现尽可能抽象。
最佳答案
听起来基本上您确实想要每个键的值列表，是的。那么添加到 map 的过程就是:
- key 存在吗？
- 如果是这样，请为现有列表添加值(value)。
- 如果没有，请在树中的适当位置(照常)创建一个新节点，并从包含一个值的列表开始
迭代 map 时，您的一般模式是:
- 生成左节点的所有值(较小的键)
- 生成该节点的所有值 - (key, value1), (key, value2) 等
- 生成右侧节点的所有值(较大的键)
当然，如果您不需要自己实现这个用于学习目的，您可以使用现成的多重映射，例如 Guava的TreeMultimap 。如果您为了自学而实现它，我会首先实现一个“正常”的二分搜索映射，然后从那里继续。
关于java - 二叉搜索树中的重复项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15448176/