Какими достаточно хорошими способами я могу вставить объект (пакет) в двоичное дерево поиска? - PullRequest
Новая
       12

Какими достаточно хорошими способами я могу вставить объект (пакет) в двоичное дерево поиска?

0 голосов
/ 21 июня 2019

Я пытаюсь вставить Packet object в это двоичное дерево поиска.Но проблема в том, что я не знаю достаточно хорошего способа сделать это или как это сделать.Я ищу несколько указателей в правильном направлении и мне нужно показать, что нужно делать для решения этой проблемы.

Пожалуйста:

  • Игнорируйте мое использование пространства имен std;потому что это в образовательных целях, и я не собираюсь (на данный момент) надеяться пойти дальше этого!
  • Помогите мне с моим конкретным вопросом и, если возможно, покажите мне, как я мог решить эту проблему.

<< <strong>Посмотрите на мой код >>

Main.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);
}

Packet.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;
};

Это была моя предыдущая реализация insert в BST.cpp: 

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

Как видите, я не верю, что это идеально.Я имею в виду, я должен был использовать & ссылку дважды.Есть ли более элегантное решение, и могу ли я получить рекомендации по этому поводу?

1 Ответ

0 голосов
/ 21 июня 2019

Q: Как я могу вставить этот объект с именем Packet в BST?

A: Чтобы создать связь между BST и классом Packet, вы должны определить ее каким-то образом.Передовая практика требует ассоциации, которая налагает наименьшее количество связей между связанными классами.

Я реализовал ассоциацию в вашем решении в месте, которое мне показалось наиболее подходящим, т.е.указатели rlink и llink структуры Node класса BST.

// Store packet here (for instance Packet *data or something)... Packet* rlink, * llink;

Отношения - это единственный способ получить доступ к getPartId () из объекта Node или BST.Хотя класс 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;
    }
}

Как я уже сказал, отношения - это единственноеспособ получить доступ к getPartId () из объекта Node или BST.

Что касается комментариев, я согласен.Инкапсуляция требует, чтобы все члены данных были приватными, и только когда это необходимо, выявляются методы.Мое решение позволяет вам сохранять функцию

частной: void insert(Node*& p, Packet* newPacket);

Поскольку вы полностью скрыли Node, перегрузив preorderTraversal()

Хорошая работа и надеюсь, что я помог!

...