c++ - BST实现的一个小问题

Question

我正在为二叉搜索树编写类似 STL 的容器。我有 Tree 本身的模板类和嵌套类 TreeNode。
我的问题是我应该将比较键的二进制谓词函数放在哪里 - 放入树类或节点类？如果我决定把它放在 Tree 类中，我的所有节点都不知道如何比较它们的键:(
如果在 Node 类中，我应该让这个函数静态还是不？

Answer 1

应该在存储在节点内的值之间进行比较，而不是在节点本身之间进行比较。因此，您在建议的任何一个地方都不需要比较器。您可以将比较器类作为树（和节点）的模板化参数，或者在比较节点内保存的值时仅依靠默认值来工作。

Answer 2

很明显，你不能让它成为静态的——如果你这样做了，那么具有两个不同比较函数的两个不同的树将不起作用（后一个会覆盖全局）。

同样清楚的是，它不应该是每个节点 - 您将无缘无故地复制完全相同的功能，每个节点都有内存命中 - 单个树中的所有节点都将具有相同的比较器。

所以最好的选择是让它成为容器的一部分。至于您反对节点无法比较自己，这有什么关系？唯一一次比较两个节点是在容器操作的上下文中，在这种情况下，您可以方便地使用比较器对象。