How to call a function method recursively in classes in c++?

user_10812040 0
Viewed 445

So, I started learning and reading about OOP not so long ago, I've been implementing all the data structures I know using classes and objects just for overall practice and to get comfortable with using OOP in c++.

I'm implementing the tree data structure and I've been wondering how to call a method recursively(I'm aware that I have to pass in an argument) so that when I create an object in main and call a specific method it's written like the following a.inorder(); and not a.inorder(root) since root is a private attribute.

Is this possible ?

My code: 

#include<iostream>
using namespace std;

struct node
{
    int data;
    node* left;
    node* right;
};

class tree
{
private:
    node* root;
public:
    tree();
    tree(int val);

    void insert(int val);
    void preorder();
    void postorder();
    void inorder();
    int count();
};

tree::tree() : root { NULL }
{
}
tree::tree(int val)
{
    root = new node;
    root->data = val;
    root->left = root->right = NULL;
}

void tree::insert(int val)
{
    if (!root)
    {
        root = new node;
        root->data = val;
        root->left = root->right = NULL;
    }

    else
    {
        node* t = root;
        node* p = NULL;

        while (t)
        {
            p = t;

            if (val > root->data)
                t = root->right;
            else
                t = root->left;
        }

        t = new node;
        t->data = val;
        t->left = t->right = NULL;

        if (p->data > t->data)
            p->left = t;
        else
            p->right = t;
    }
}
void tree::preorder()
{
    if (root)
    {

    }
}
oop c++
4 Answers

In your design, a node refers to itself. Since it is the node object that is recursive, you could define the recursive method on node:

struct node
{
    int data;
    node* left;
    node* right;

    void preorder() {
        //...
        left->preorder();
        right->preorder();
    }
};

And then, tree::preorder() would just dispatch a call to root->preorder().

user_3150520

Write a private static recursive function passing to it the pointer to the root node and call the function from the corresponding public non-static member function.

For example

public:
    std::ostream & preorder( std::ostream &os = std::cout ) const
    {
        return preorder( root, os );
    }
    //...

private:
    static std::ostream & preorder( const node *root, std::ostream &os );
    //...
user_28772410

This is a comment rather than an actual answer, as it addresses a different issue than you are asking about. However, it is too long for a comment space, that's why I post it here.

I suppose you erroneously refer to root in this part

        while (t)
        {
            p = t;

            if (val > root->data)
                t = root->right;
            else
                t = root->left;
        }

IMHO it should look like this:

        while (t)
        {
            p = t;

            if (val > t->data)
                t = t->right;
            else
                t = t->left;
        }

Also compare the code to seek a place for insert with a code that makes an actual insertion:

        if (p->data > t->data)
            p->left = t;
        else
            p->right = t;

You've put a comparison subexpressions in reversed order - when seeking, you test whether the new value is greater than that in an existing node, but when inserting, you test whether the existing value is greater than the new one. If they differ, the code will work OK, because you also swapped left and right in the 'then' and 'else' branch.
However, if the values appear equal, the execution control will go to 'else' in both places. As a result the testing code may stop at empty left pointer, but then a new node would get appended to the right, which was not tested for being NULL.

user_7336370

Why would the tree class do intrinsic operations on node? The node class knows best the node's internal structure, so let it initialize itself. This will also help you to stick to the DRY principle and, indirectly, to the KISS principle, as well as the Single-responsibility principle.

struct node
{
    int data;
    node* left;
    node* right;

    node(int val) : data(val), left(NULL), right(NULL) {}        
};

class tree
{
private:
    node* root;
public:
    tree();
    tree(int val);

    void insert(int val);
};

tree::tree() : root { NULL }
{
}

tree::tree(int val) : root(new node(val))
{
}

void tree::insert(int val)
{
    if (!root)
    {
        root = new node(val);
    }
    else
    {
        node* t = root;
        node* p = NULL;
        
        while (t)
        {
            p = t;
            
            if (val < t->data)
                t = t->left;
            else
                t = t->right;
        }
        
        t = new node(val);
        
        if (t->data < p->data)
            p->left = t;
        else
            p->right = t;
    }
}

Additionally, you can make insert recursive, too.

struct node
{
    int data;
    node* left;
    node* right;

    node(int val) : data(val), left(NULL), right(NULL) {}        
};

class tree
{
private:
    node* root;
public:
    tree();
    tree(int val);

    void insert(int val);
protected:
    void insertat(node* p, int val);
};

void tree::insert(int val)
{
    if (!root)
        root = new node(val);
    else
        insertat(root, val);
}

void tree::insertat(node* t, int val);
{
    if (val < t->data)
    {
        if (t->left)
            insertat(t->left, val);
        else
            t->left = new node(val);
    }
    else
    {
        if (t->right)
            insertat(t->right, val);
        else
            t->right = new node(val);
    }
}
user_7336370
Related