Binary Search Tree to store objects now with improvements

Question

Objective:

I'm trying to create a BST in order to insert Packet objects for search purposes. Packet holds information like partId, description, price, and partCount.

This is a follow up question of this post. I have since revised it so that:

• No or minimal memory leaks
• Includes minimized
• Namespace usage is minimized or removed altogether

Now I want to ask some more questions:

As you can see here,

void BST::insert(Packet &data) {

I have to do this within the function,

newNode->data = &data;

Is there a way to make that a more elegant solution or improve it? Because as you can see I'm using reference twice and I'd like to fix that or improve it. Could I get an example or be shown how this could be fixed?

In an answer to the other post, it was said:

Node isn't part of the public interface. If we make it a private struct within BST, then BST gets full access (not needing a friend declaration), but no other code does. That's what we really want.

I have never done this before. Could I be shown an example or directly?

Main.cpp:

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

using namespace std;

int main() {
    BST test1;
    cout << "-------------------------------------------------------" << endl;
    cout << "Testing BST" << endl;
    cout << "-------------------------------------------------------" << endl;
    Packet packetTest(123, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest1(321, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest2(456, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest3(7, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest4(119, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest5(456, "This is a packet of cheese.", 12.95, 10);
    test1.insert(packetTest);
    test1.insert(packetTest1);
    test1.insert(packetTest2);
    test1.insert(packetTest3);
    test1.insert(packetTest4);
    test1.insert(packetTest5);
    test1.preorderTraversal();
    system("pause");
}

BST.h:

#pragma once

#include "Packet.h"

class Node
{
    friend class BST;
public:
    Node() : data(nullptr), rlink(nullptr), llink(nullptr) {}
    ~Node() {}

private:
    Packet *data;
    Node *rlink, *llink;
};

class BST {
public:
    BST();
    void BST::insert(Packet &data);
    void BST::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) {}

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

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

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

void BST::preorderTraversal(const Node *p) const {
    if (p != nullptr) {
        std::cout << p->data->getPartId() << " ";
        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>

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

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

Answer 1

Here are some things that may help you improve your code.

Remove extra qualifications in class member declarations

My compiler complains:

error: extra qualification ‘BST::’ on member ‘insert’

and it is absolutely right. What it's pointing out is that this line,

void BST::insert(Packet &data);

coming as it does within the declaration of the BST class, should not have the BST:: prefix. Instead just write it like this:

void insert(Packet &data);

It might compile with your compiler (today anyway), but it's an error and should be fixed.

Use include guards

There should be an include guard in each .h file. That is, start the file with:

#ifndef BST_H
#define BST_H
// file contents go here
#endif // BST_H

The use of #pragma once is a common extension, but it's not in the standard and thus represents at least a potential portability problem. See SF.8

Don't use system("pause")

There are two reasons not to use system("cls") or system("pause"). The first is that it is not portable to other operating systems which you may or may not care about now. The second is that it's a security hole, which you absolutely must care about. Specifically, if some program is defined and named cls or pause, your program will execute that program instead of what you intend, and that other program could be anything. First, isolate these into a seperate functions cls() and pause() and then modify your code to call those functions instead of system. Then rewrite the contents of those functions to do what you want using C++. An example:

void pause {
    std::getchar();
}

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use constant string concatenation

The main routine currently has these lines:

cout << "-------------------------------------------------------" << endl;
cout << "Testing BST" << endl;
cout << "-------------------------------------------------------" << endl;

But you don't really need to do it that way which potentially calls the << operator six times. Instead, you could express the same thing as this:

std::cout <<
        "-------------------------------------------------------\n" 
        "Testing BST\n"
        "-------------------------------------------------------\n";

This only calls << once. The compiler automatically concatenates the string literals together.

Rethink the interface

Do interfacing programs really need for this method to be public?

void insert(Node *&p, Node *newNode);

I would say they do not, and that further, Node is an implementation detail that could be a private class within BST. Also, the zero-argument destroyTree seems entirely redundant; you already have a destructor with identical code. Here's how to make the Node private:

class BST {
    struct Node {
        Packet *data = nullptr;
        Node *rlink = nullptr, *llink = nullptr;
    };

Prefer in-class initializers to trivial constructors

As shown above, the Node class above can be quite trivially rewritten as a struct with no explicit constructor or destructor. We let the compiler provide defaults. See C.45 for details.

Decide on ownership

When a Packet is given to the tree, does the tree own it? That is, when the tree is destroyed, should the Packets also be destroyed? If the answer is yes, which is the usual case, then there should be a move constructor for Node. If the answer is no, then you should be using a std::shared_ptr or the like. In almost no case should you be passing and storing pointers to references. I would suggest looking carefully at the interfaces for standard containers such as std::vector and std::array and emulate those.

Fix the bug

The current code has a problem. When the second item with a part ID of 456 is added, we get a tree like this. In this diagram, left links are green and right links are red. The right link that points from the 456 node to itself is an error which breaks the tree. Binary trees must have no loops.