2

2 種類のオブジェクトに BST を実装する必要があります。アカウントと顧客。これらのタイプはどちらも pk (どちらも「id」と呼ばれます) を持っています。解決策をグーグル/リサーチすると、たくさんの BST 解決策を見つけることができますが、それらはすべて単純な型で動作するようです。たとえば、BST 解決策は {1,2,3,4,99,...999 のような整数をソートできます。 }-しかし、BSTソリューションで、pkに基づいて複雑なタイプ/クラスをソートしたいと考えています。これは可能ですか / 何かヒントはありますか? ありがとう。

4

2 に答える 2

4

整数の二分探索木を構築するために使用されるロジックは、すぐに他のデータ型に一般化できるはずです。各ノードに整数をキーとして保存する代わりに、顧客名とアカウント名を各フィールドに保存しますが、ルックアップを行うときは主キーのみを比較します。それは本当に簡単なはずです。

とはいえ、これが宿題でない限り、std::map を使用する必要があります。これは、バイナリ サーチ ツリーと同じ複雑さの保証をすべて備えていますが、すでに作成されており、広く利用可能で、十分にテストされています。

お役に立てれば！

于 2013-01-04T17:09:25.927 に答える
3

1 つの方法は、ノード定義を変更して、保存するオブジェクトへの参照を追加し、インデックス (この場合は 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;
}

ツリー内で異なるオブジェクト タイプを混在させたい場合、もう 1 つの方法は、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 またはツリー構造の別の既知のライブラリを使用することを検討してください。

于 2013-01-04T17:30:43.553 に答える