java - 二叉搜索树中的重复项

Question

在二叉搜索树中处理重复项的优雅方法是什么？让我们假设每个键都有几个不同的关联值。我需要做的是按顺序遍历所有值。因此，如果我有 2 个值 A 和 B 与键 1，以及一个值 C 与键 2，我想得到对：（1，A），（1，B），（2，C），当调用类似TreeIterator.next();

我能想到：

• 每个节点都有一个键和一个值数组，其中具有相同键的值
• 每个节点都有一个visited标志

还有其他建议吗？作为一般准则，我希望 Tree 实现尽可能抽象。

Answer 1

听起来基本上你确实想要每个键的值列表，是的。所以添加到地图的过程是：

• 密钥存在吗？
  • 如果是这样，请将值添加到现有列表中。
  • 如果没有，请在树中的适当点（正常）创建一个新节点，并从一个值的列表开始

遍历地图时，您的一般模式是：

• 从左节点产生所有值（较小的键）
• 产生此节点的所有值 - (key, value1), (key, value2) 等
• 从右节点产生所有值（较大的键）

当然，如果您不需要出于学习目的自己实现此功能，则可以使用现成的多图，例如Guava的TreeMultimap. 如果你是为了自学而实现它，我会从实现一个“正常”的二进制搜索映射开始，然后从那里继续。