如何為復雜型別創建允許在C 中重復的二叉搜索樹？

我已經閱讀了許多關于 BST 和重復項的帖子，我知道這不太可能/沒有干凈的方法來允許重復項，尤其是對于我正在使用的復雜型別。所以我需要一些關于如何/是否可以在我的場景中使用重復的 BST 的幫助。

我的場景：我使用 Transaction 類作為我的節點鍵，我比較的主要資料是事務類中的“金額”，因此我的二叉搜索樹可以允許您輸入金額并輸出任何帶有其 ' 的交易toString()' 函式給用戶，匹配搜索量。但是，現在我面臨的問題是我將無法擁有重復的交易金額。我怎么能解決這個問題？誰能提供一個例子？謝謝。

代碼復現問題解決：

#include<iostream>
using namespace std;
#include <algorithm>
#include <cctype>
#include <string>
#include <memory>

// Complex type used for the BST
class Transaction
{
private:
    std::string desc;
    time_t timestamp;
    std::string value;
    bool isWithdrawal;

public:

    Transaction(const std::string& value, std::string reason = "None.")
    : desc(reason), timestamp(time(nullptr)), value(value) { // timestamp is current date/time based on current system

        // Lambda to convert reason to lower to we can identify elements easier
        std::transform(reason.begin(), reason.end(), reason.begin(),
            [](unsigned char c) { return std::tolower(c); });
    
        this->isWithdrawal = (reason.find("withdrawal") != std::string::npos) ? true : false;
    } 

    std::string toString() const {
        // convert timestamp to string form
        const char* string_timestamp = ctime(&timestamp);
    
        if(this->isWithdrawal) { return "-- "   desc   ": -￡"   value   " on "   string_timestamp;}
        else {return "-- "   desc   ": ￡"   value   " on "   string_timestamp;}
    }
    
    // Gets the amount, converts it to a double and returns it
    double getAmount() const {
        return std::stod(this->value);
    }
};


// The binary search tree implementation
class BST {
    
    struct node {
        std::shared_ptr<Transaction> data;
        node* left;
        node* right;
    };

    node* root;

    node* makeEmpty(node* t) {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(std::shared_ptr<Transaction> x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x->getAmount() < t->data->getAmount())
            t->left = insert(x, t->left);
        else if(x->getAmount() > t->data->getAmount())
            t->right = insert(x, t->right);
        return t;
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t) {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    void inorder(node* t) {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->data->getAmount() << " ";
        inorder(t->right);
    }

    node* find(node* t, double x) {
        if(t == NULL)
            return NULL;
        else if(x < t->data->getAmount())
            return find(t->left, x);
        else if(x > t->data->getAmount())
            return find(t->right, x);
        else
            return t;
    }

public:
    BST() {
        root = NULL;
    }

    ~BST() {
        root = makeEmpty(root);
    }

    void insert(std::shared_ptr<Transaction> x) {
        root = insert(x, root);
    }

    void display() {
        inorder(root);
        cout << endl;
    }

    std::string search(double x) {
        node* result = find(root, x);
        if(result != NULL) { return result->data->toString(); }
        else { return "N/A"; }
    }
};

int main() {
    BST t;
    t.insert(std::make_shared<Transaction>("1500.50", "Deposit"));
    t.insert(std::make_shared<Transaction>("1600.98", "Deposit"));
    t.insert(std::make_shared<Transaction>("1400", "Withdrawal"));
    t.insert(std::make_shared<Transaction>("1400.59", "Deposit"));
    t.display();
    
    std::cout << t.search(1500.50);
    
    return 0; 
}

uj5u.com熱心網友回復：

我已經閱讀了許多關于 BST 和重復項的帖子，我知道這不太可能/沒有干凈的方法來允許重復項，尤其是對于我正在使用的復雜型別。

這是不正確的，您可以使用multimap或multiset在這種情況下。

例如，cppreference

Multimap 是一個關聯容器，它包含鍵值對的排序串列，同時允許具有相同鍵的多個條目。排序是根據應用于鍵的比較函式比較完成的。搜索、插入和洗掉操作具有對數復雜性。

您只需要提供一個Compare函子作為模板引數，該函子表示對于兩個等效鍵，沒有一個小于另一個。

uj5u.com熱心網友回復：

您可以通過使您的data成員成為容器來將 BST 節點與多個值關聯，例如，更改：

std::shared_ptr<Transaction> data;

進入

std::list<std::shared_ptr<Transaction>> data;

這與將一個鍵與多個值相關聯是一樣的。本質上，這就是做什么std::multimap和std::multiset做什么。您還必須更新樹操作/迭代器。std::list例如，在進行容器遍歷時，您必須將各個s壓縮在一起。

編輯：

一個簡單的替代方法是使用std::multiset<std::tuple<std::string, time_t, std::string, bool>>.

uj5u.com熱心網友回復：

二叉搜索樹可讓您存盤鍵和相關記錄。它允許對給定鍵進行有效搜索（目的是檢索相關資訊）。

由于它還支持按排序順序列舉，因此它允許檢索給定范圍內的所有鍵，并且重復鍵不是問題。

標籤：算法 哎呀 指针

上一篇：在不知道其子結構的大小的情況下為結構的指標分配記憶體是否有效？

下一篇：掃描字串的功能-有什么問題？