c++ - 有哪些足够好的方法可以将对象(数据包)插入二叉搜索树？

Question

我正在尝试将一个 Packet 对象 插入到这个二叉搜索树中。但问题是，我真的不知道这样做的足够好方法或如何着手去做。我正在寻找一些正确方向的指示，并向他们展示如何解决这个问题。

请:

• 忽略我对命名空间标准的使用；因为这是为了教育 目的，我不打算(截至目前)走得更远!
• 帮我解决我的具体问题，如果可能的话，告诉我我是怎么做的 可以解决这个问题。

<<看看我的代码>>

主要.cpp:

#include <iostream>

#include "BST.h"
#include "Packet.h"

// IGNORE the USAGE of namespace std. as this is purely a testing program for educational purposes.
// It is NOT implementation for a real program.
using namespace std;

int main() {
    cout << "-------------------------------------------------------" << endl;
    cout << "Testing BST" << endl;
    cout << "-------------------------------------------------------" << endl;
    BST test1;
    Packet packetTest(123, "This is a packet of cheese.", 12.95, 10);
    // test1.insert(How should I choose to insert Packet? That's the question.);
    system("pause");
}

BST.h:

#pragma once

#include "Packet.h"

using namespace std;

class BST {
    struct Node {
        Node() : rlink(nullptr), llink(nullptr) {};
        ~Node() {};

        // Store packet here (for instance Packet *data or something)...
        Node *rlink, *llink;
    };
    public:
        BST();
        // void insert(How should I choose to insert Packet? That's the question.);
        void insert(Node *&p, Node *newNode);
        void preorderTraversal() const;
        void destroyTree();
        ~BST();
    private:
        Node * root;
        void destroyTree(Node *&p);
        void preorderTraversal(const Node *p) const;
};

BST.cpp (此处需要指导，请参阅下面的代码以了解我的意思):

#include "BST.h"
#include <iostream>

BST::BST() : root(nullptr) {}

// Need guidance here. What should I do for this function? How can I insert this object called Packet into the BST? 
/*void BST::insert(How should I choose to insert Packet? That's the question.) {
    Node *newNode = new Node;
    ...
    insert(root, newNode);
}*/

void BST::insert(Node *&p, Node *newNode) {
    if (p == nullptr) {
        p = newNode;
    }/*else if (p's data's getPartId() > newNode's data's getPartId()){
        insert(p->llink, newNode);
    }*/else {
        insert(p->rlink, newNode);
    }
}

void BST::preorderTraversal() const {
    if (root == nullptr) {
        cerr << "There is no tree.";
    }
    else {
        preorderTraversal(root);
    }
}

void BST::preorderTraversal(const Node *p) const {
    if (p != nullptr) {
        // cout << p->data->getPartId() << " "; Need to handle Packet's data here. But we need to implement Packet insection first!
        preorderTraversal(p->llink);
        preorderTraversal(p->rlink);
    }
}

void BST::destroyTree(Node *&p) {
    if (p != nullptr) {
        destroyTree(p->llink);
        destroyTree(p->rlink);
        delete p;
        p = nullptr;
    }
}

void BST::destroyTree() {
    destroyTree(root);
}

BST::~BST() {
    destroyTree(root);
}

数据包.h:

#pragma once
#include <string>

using namespace std;

class Packet {
public:
    Packet(int partId, string description, double price, int partCount) :
        partId(partId), description(description), price(price), partCount(partCount) {}
    int getPartId() const { return partId; }

private:
    int partId;
    string description;
    double price;
    int partCount;
};

这是我之前在 BST.cpp 中插入的实现:

void BST::insert(Packet &data) {
    Node *newNode = new Node;
    newNode->data = &data;
    insert(root, newNode);
}

如您所见，我认为这并不理想。我的意思是我不得不使用 & 引用两次。有没有更优雅的解决方案，我可以得到这方面的指导吗？

Answer 1

问:如何将这个名为 Packet 的对象插入到 BST 中？

A:要在 BST 和 Packet 类之间建立关系，您必须以某种方式定义一个。最佳实践要求关联在相关类之间施加最少的耦合。

我在您的解决方案中我发现最合适的地方实现了关联，即。类 BST 的 struct Node 的 rlink 和 llink 指针。

//在此处存储数据包(例如 Packet *data 或其他)... 数据包* rlink, * llink;

关系是您能够从 Node 或 BST 对象访问 getPartId() 的唯一方式。尽管 Packet 类不管理任何资源，因此不需要内存管理，但关联只是类之间松散耦合关系的一个奇特的词，这里就是这种情况。

递归调用函数时要小心，正如您在 void BST::insert(Node *&p, Node *newNode) 中所做的那样。您不应该在没有退出条件的情况下递归调用函数，并且永远不要真正使用递归，除非您必须这样做，因为迭代是一种节省堆栈内存的替代方法。我看到你的插入函数不需要递归，所以我把它拿出来了。我希望我替换它们的内容对您有用:

void BST::insert(Packet& p) {
    Packet* newPacket = new Packet(p);
    insert(root, newPacket);
}

void BST::insert(Node*& p, Packet* newPacket) {
    if (p == nullptr) {
        p = new Node;
        p->llink = newPacket;
    }else if ((p->llink->getPartId()) > newPacket->getPartId()){
        p->llink = newPacket;
    }else {
        p->rlink = newPacket;
    }
}

然后我接着说:

void BST::preorderTraversal(const Node* p) const {
    if (p != nullptr) {
        cout << p->llink->getPartId() << " \n";
    }
}

void BST::destroyTree(Node*& p) {
    if (p != nullptr) {
        delete p;
        p = nullptr;
    }
}

正如我所说，关系是您能够从 Node 或 BST 对象访问 getPartId() 的唯一方式。

关于评论，我同意。封装要求将所有数据成员保持私有(private)，并且只在必要时公开方法。我的解决方案允许您保留功能

private:void insert(Node*& p, Packet* newPacket);

由于您通过重载 preorderTraversal()

完全隐藏了 Node

干得好，希望我有所帮助!