在C++中，我可以使用对象/结构作为节点创建二叉搜索树吗？-解网

问：

在其他相关的 c++ 工作中，我设法创建了一种二叉搜索树模板。这里的含义是，使用这个模板，我可以为各种数据类型创建一个 BST......Int、字符串等。我被要求使用 BST 作为数据结构。让我们想象一下这是天气数据。测量设备每天多次记录温度，因此我有日期和时间以及温度。每条记录我都想使用一个结构作为容器，所以我想要这样的东西：

struct Record 
{
string DateTime;
float temperature;
};

DateTime 在这里是一个字符串，因为它的格式类似于 dd/mm/yyyy xx：xx。我也许可以将其转换为 int。

有数千条记录，我想将它们全部插入我的 BST 中。这是行不通的，我的 BST 模板不知道如何比较 2 条记录来判断哪一条将进入左链接和右链接。我可以只写一个布尔运算符>函数，它将接受 2 条记录，比较两者的日期时间，然后说稍后制作的记录是否“大于”之前制作的记录，因此它进入这里的树等等？这一般会起作用吗？

我是否应该做一些事情，比如创建一个映射，其中包含一个名为 DateTime 的 int 与记录配对，然后将所有表示 DateTimes 的整数值插入我的 BST。然后，当我需要取回我的数据时，首先我搜索 BST 以检查是否有条目，然后将该结果用于我的地图，然后它应该为我提供我想要的对象。

我之所以需要做这一切，是因为我想进行计算，例如“给我 2018 年每个月的平均温度”。然后我会搜索我的 BST，将 2018 年每个月的所有日期时间都还给我，然后通过地图访问我的记录以计算温度并取平均值。

请随时为我指出正确的方向。我发现谷歌搜索如何创建对象和结构的 BST 给了我使用整数节点实现 BST，这还不够......？

C++ 二进制搜索树

它更常用于比较，您应该编写 BST 以以这种方式使用比较。所以宁愿写成.您可以向 BST 添加一个额外的模板参数，并将其用于比较。您也可以将其默认为，这样它将成为可选的，并在 BST 的数据类型具有 BST 时使用。operator <a > bb < aauto comparestd::lessoperator <

1赞 Goswin von Brederlow 7/30/2022

您不应该将结构转换为插入到 .这就是你制作模板的原因，这样你就不必做这样的事情了。它应该只是一个 .如果您还实现了与 en.cppreference.com/w/cpp/algorithm/upper_bound 年第 2 版匹配的模板函数，那么从 2018 年开始积累所有 s 就变得微不足道了。RecordintBSTBSTBST<Record>lower_boundupper_boundRecord

答：

1赞 trincot 7/30/2022 #1

DateTime 在这里是一个字符串，因为它的格式类似于 dd/mm/yyyy xx：xx。我也许可以将其转换为 int。

你可以。

我可以只编写一个布尔运算符函数来获取 2 条记录，比较两者的日期时间，然后说稍后制作的记录是否“大于”之前制作的记录，因此它进入这里的树等等？这一般会起作用吗？>

是的，它会的。

我是否应该做一些事情，比如创建一个地图，其中包含一个名为 DateTime 的 int 与记录配对

这是一种可能性，尽管它不应该是一个单独的数据结构。BST 中的一个节点将由键入，并将关联的 Record 作为有效负载（因此 a 带有 an 和 a）。或者，如果空间效率是一个问题，您可以仅将它与温度（再次作为）配对。然后定义一个可以将日期字符串转换为日期字符串的函数。intstructintRecordintstructint

另一种替代方法是将 DateTime 字符串格式更改为 ISO 8601 格式：yyyy-mm-ddThh：mm：ss，并在数据源中执行此操作，因此无需来回转换。

这有两个优点：

这是一个很好的标准，得到了许多服务/库/API 的支持
词法顺序是您期望的日期/时间顺序。这意味着您不再需要转换为，但可以将记录用作 BST 中的节点，只需将日期与字符串比较即可。int

0赞 Emil Lang 8/2/2022 #2

正如 trincot 所指出的，有很多方法可以使用带有结构的二叉搜索树。我牢记，我不应该使用单独的结构来存储我的记录，因为他们正确地指出，使用我的 BST 模板，它通常应该声明为 BST< Record > 而不是 BST< int >。

在我前面的例子中，我使用了一个结构来存储记录数据。我决定改用一个类。在我的新 Record 类中，我添加了运算符函数，以便我的 BST 模板知道在比较 2 个对象时该怎么做。

想象一下，我的新 Record 类如下所示：

class Record
{
    public:
        /* 
        member variables
        */
        void printValues();
        bool operator>(const Record& otherRecord) const;
        bool operator==(const Record& otherRecord) const;
};

ostream & operator<<(ostream &out, const Record &REC);
//implementation below
bool Record::operator>(const Record& otherRecord) const
{
    return (date > otherRecord.date);
}

bool Record::operator==(const Record& otherRecord) const
{
    return (date == otherRecord.date);
}

如您所见，我重载了 > 和 == 运算符。例如，在我的模板中，使用这些运算符的函数如下所示（这只是其中一个用于说明的函数）：

template<class T>
void BSTTemplate<T>::insert(const T& insertItem)
{
    Node<T>* current;
    Node<T>* trailCurrent;
    Node<T>* newNode;

    newNode = new Node<T>;
    newNode->info = insertItem;
    newNode->leftLink = nullptr;
    newNode->rightLink = nullptr;

    if (root == nullptr)
        root = newNode;
    else
    {
        current = root;
        while (current != nullptr)
        {
            trailCurrent = current;
            if(current->info == insertItem)
            {
                cout << "Item is already in tree. Duplicates not allowed." << endl;
                return;
            }
            else if(current->info > insertItem)
                current = current->leftLink;
            else
                current = current->rightLink;

        }
        if (trailCurrent->info > insertItem)
            trailCurrent->leftLink = newNode;
        else
            trailCurrent->rightLink = newNode;
    }
}// end insert()

如果没有重载运算符，像

if(current->info == insertItem)

和

else if(current->info > insertItem)

不适用于我希望创建和使用的对象。

其他用户建议我应该输入一个帮助我解决问题的答案，所以你去吧！希望能帮助别人......

上一个：在 C++ 中，如何使用作为对象数组的私有变量？

下一个：如果我编写一个函数指针以在 BST 模板中使用，他们可以接受 1 个以上的对象作为参数吗？

在C++中，我可以使用对象/结构作为节点创建二叉搜索树吗？

In C++ can I create a Binary Search Tree using objects/structs as the node?

评论