c++ - C++ 二叉搜索树 - 复杂类型

Question

我需要为 2 种类型的对象实现 BST；帐户和客户。这两种类型都有一个 pk（都称为“id”）。当我 google/research 寻找解决方案时，我可以找到大量 BST 解决方案，但它们似乎都适用于简单类型，例如 BST 解决方案可以对 {1,2,3,4,99,...999 等整数进行排序- 但我希望 BST 解决方案根据它们的 pk 对复杂类型/类进行排序。这可能/任何提示？谢谢。

Answer 1

用于构建整数二叉搜索树的逻辑应该可以立即推广到其他数据类型。不是在每个节点中存储一个整数作为键，而是在每个字段中存储您的客户和帐户名称，但在进行查找时只比较主键。真的应该这么简单。

也就是说，除非这是用于家庭作业，否则您应该只使用 std::map，它具有与二叉搜索树相同的复杂性保证，但已经为您编写、广泛可用且经过大量测试。

希望这可以帮助！

Answer 2

一种方法是修改节点定义，添加对要存储的对象的引用并设置索引（在您的情况下为 pk），以对注释进行排序。在使用不同类型时，模板可能会解决：

class Account
{
    public:
        Account(int k) : pk(k) {};
        int pk;
    /* ... */
};


template<typename T>
class TreeNode
{
    public:
        TreeNode(T& the_object) : id(the_object.pk), object(the_object) {};

        int id;
        T& object;
};


int main () {
    Account a(9);
    TreeNode<Account> tn(a);
    std::cout << tn.id;
}

如果要在树中混合不同的对象类型，另一种方法是定义一个包含 pk 属性访问器的类，并将帐户和客户置于其中，例如：

class Indexable
{
    public:
        Indexable(int the_pk) : pk(the_pk) {};
        int pk;
};

class Account : public Indexable
{
    public:
        Account(int k) : Indexable(k) {};
    /* ... */
};

class TreeNode
{
    public:
        TreeNode(Indexable& the_object) : id(the_object.pk), object(the_object) {};

        int id;
        Indexable& object;
};


int main () {
    Account a(9);
    TreeNode tn(a);
    std::cout << tn.id;
}

正如其他答案所指出的，在生产中，您可能会考虑使用 std::map 或其他已知的树结构库。