Object-oriented Programming error?

Question

I've a question with my homework, I need to do a project in C++, and I need to use Object-oriented Programming, it's a vocabulary with a Binary Search Tree, and I finished it. But I use a struct... with it I break the OOP rules? If yes, how can I convert the struct in an inherited class?

template <typename T>
struct BinaryNode
{
    T key;
    BinaryNode<T>* left;
    BinaryNode<T>* right;
    BinaryNode<T>* parent;
};

template <typename T>
class BinarySearchTree
{
private:
    BinaryNode<T>* root;
    BinaryNode<T>* newNode(T key);
public:
    BinarySearchTree();
    ~BinarySearchTree();

    void insert(T key);
    BinaryNode<T>* search(T key);
    void distance(T key);
    void inorderTreeWalk();

    void insert(BinaryNode<T>** node, T key);
    BinaryNode<T>* search(BinaryNode<T>* node, T key);
    void distance(BinaryNode<T>* node, T key);
    void inorderTreeWalk(BinaryNode<T>* node);
    BinaryNode<T>* remove(BinaryNode<T>* node);

    BinaryNode<T>* minimum(BinaryNode<T>* node);
    BinaryNode<T>* maximum(BinaryNode<T>* node);
    BinaryNode<T>* successor(BinaryNode<T>* node);
    bool contains(T key);

    BinaryNode<T>* getRoot();
};

Does your homework actually require you to write your own binary tree? Because `std::set` ought to work for most purposes. — Sebastian Redl, Feb 12 '14 at 12:25

score 3 · Accepted Answer · answered Feb 12 '14 at 11:58

3

No, you don't "break" OOP rules by using struct.

In C++ structs and classes are basically the same thing, the only difference being the default visibility for their members. ( classes members are private by default while structs members are public by default. )

answered Feb 12 '14 at 11:58

Tiago Gomes

386
2
7

Yes, i know, but with struct the members are public, and for OOP i don't break the encapsulated state? – Raid3nz Feb 12 '14 at 12:03
1

@Raid3nz The encapsulation breakage isn't caused by the publicness of the node's fields, but by the fact that one can reach into the tree and get at its nodes. As a user, it's easy to turn your BST into something that isn't a BST at all. – molbdnilo Feb 12 '14 at 12:24
1

@Raid3nz - Yes, you do, and badly. You are returning modifiable pointers to `BinaryNode` objects. A user can modify the root node, for example and make the tree into a non-tree. – David Hammen Feb 12 '14 at 12:26

score 1 · Answer 2 · answered Feb 12 '14 at 12:06

1

No you don't.

In your example you can change struct for class and you won't have any problem(modify the visibility of the attributes or create new methods to access/modify them).

answered Feb 12 '14 at 12:06

Jose Palma

756
6
13

score 1 · Answer 3 · answered Feb 12 '14 at 12:21

You are not breaking OOP rules. However because struct BinaryNode is used only in context of BinarySearchTree class it's better to make it a nested class, in such a way the internals of your realization of BinarySearchTree class would be hidden:

template <typename T>
class BinarySearchTree
{
private:
    template <typename T> struct BinaryNode
    {
        T key;
        BinaryNode<T>* left;
        BinaryNode<T>* right;
        BinaryNode<T>* parent;
    };
...

Object-oriented Programming error?

3 Answers3