Traversing a tree class from a function

Question

I have a tree class - see bellow - I'd like to traverse and do some processing from a function outside the tree class. In order to traverse the tree I need to set a pointer to the root of the tree. However I can't access the root outside the class since its private.

Is there a way to do this elegantly without using a getter - to retrieve the root address - and without making the root public?

thanks for your help.

template <class Key> class IntervalST
{
private:
    Interval<Key> *root;

    bool isRed(Interval<Key> *interval);
    Interval<Key> *rotateLeft(Interval<Key> *h);
    Interval<Key> *rotateRight(Interval<Key> *h);
    Interval<Key> *put(Interval<Key> *h,Key lo, Key hi, Key val);
    Interval<Key> *moveRedLeft(Interval<Key> *h);
    Interval<Key> *moveRedRight(Interval<Key> *h);
    Interval<Key> *deleteMin(Interval<Key> *h, Key hi);
    Interval<Key> *balance(Interval<Key> *h);
    Interval<Key> *remove(Interval<Key> *h, Key lo, Key hi);
    Interval<Key> *min(Interval<Key> *h);
    Interval<Key> *addDuplicate(Interval<Key> *h, Key hi);
    Interval<Key> *removeDuplicate(Interval<Key> *h, Key low, Key hi);
    Interval<Key> *getPointerToKey(Key low);

    void flipColors(Interval<Key> *h);
    void destroy(Interval<Key> *h);
    void printTree(Interval<Key> *h, int indent);
    Key maxVal(Interval<Key> *h);
    int size(Interval<Key> *h);
    bool isBST(Interval<Key> *x, Key min, Key max);
    inline bool isBST(){return isBST(root,0,0);}
    bool isSizeConsistent(Interval<Key> *x);
    inline bool isSizeConsistent(){return isSizeConsistent(root);}
    bool is23(Interval<Key> *x);
    inline bool is23(){return is23(root);}
    bool isBalanced();
    bool isBalanced(Interval<Key> *x,int black);
    int getKeySize(Key low);
    int compare(Key a, Key b);

public:

    //don't forget to build the constructor
    //and overload the =equal operator
    IntervalST():root(NULL){};
    ~IntervalST();
    void remove(Key lo, Key hi);
    void put(Key lo, Key hi);
    inline int size(){return size(root);}
    inline bool isEmpty(){return root == NULL;}
    void print(int indent = 0);
    void check();

};

score 3 · Answer 1 · edited May 23 '17 at 12:03

3

What you want is an iterator for your class. It will most likely be defined as a friend so it can see the internals. Otherwise you need to expose methods for access.

Defining iterator of my own container for details.

edited May 23 '17 at 12:03

Community

1
1

answered Dec 12 '13 at 21:00

Sean Perry

3,776
1
19
31

I don't want to modify my tree class. I want to use it as a **black box**. Adding a friend method will "break" my black box. – PhonoDots Dec 12 '13 at 21:04
No, the iterator is defined as a friend to the container class. Follow the docs I gave you and look at some of the existing STL or Boost containers. – Sean Perry Dec 12 '13 at 21:06

Ilya Kobelevskiy · Accepted Answer · 2013-12-12T21:22:37.550

3

You can add method that accepts function pointer to your tree class, so that you can pass it a functor which will be executed on each node of your tree. This keeps traversing encapsulating within a tree, while allowing passing pointer to any function to be executed on each node.

Like this:

void IntervalST::executeOnEachNode(void (*functor)(Interval<Key> node,void* userData),
                                   void *userData = 0)
{
      Interval<Key> node;

      //Loop to traverse your tree stepping through each node
     {
       //Calls functor with supplied user data on specific node ( 
       functor(node,userData);
     }
}

Where functor is pointer to function accepting one argument (of void*) - userData, which can be used to pass bundled additional arguments to the function if required.

Use case (counts all tree nodes):

void countAllNodes(Interval<Key> node,void* additionalIntArgument)
{
    int* count = static_cast<int*>(additionalIntArgument);
    *count += 1;
}

IntervalST<double> tree;

int count(0);
tree.executeOnEachNode(countAllNodes,reinterpret_cast<void*>(&count));
std::cout << "Tree has "<<count << " nodes "<<std::endl;

edited Dec 12 '13 at 21:22

answered Dec 12 '13 at 21:00

Ilya Kobelevskiy

5,245
4
24
41

It sounds to be what I'm looking for!... But I have no idea how to do this!... Can you explain what you mean by editing the question? or even send me some links explaining the idea in more details - thanks. – PhonoDots Dec 12 '13 at 21:07
Note you will need a new method or a flag to the method for each type of tree traversal -- post order, pre order, etc. – Sean Perry Dec 12 '13 at 21:16
@PhonoDots - please see edit. Idea is implement generic traversal inside the tree, and allow passing pointer to any function to that method - which would ensure that function passed as argument will be executed on each tree node. As Sean Perry mentioned, if order of traversal is important, several such members need to be implemented for each traversal order. – Ilya Kobelevskiy Dec 12 '13 at 21:20
Seems to be what I'm looking for... Do you have some links explaining this method with more details. It's the first time I see something like this and it look fairly complicated to me - some tutorial links will help understanding it further - thanks. – PhonoDots Dec 12 '13 at 21:27
@PhonoDots The only concept used here is function pointer - try googling for "Function Pointers C++" for additional info, first link that comes up (http://www.cprogramming.com/tutorial/function-pointers.html) looks good. – Ilya Kobelevskiy Dec 12 '13 at 21:33

Traversing a tree class from a function

2 Answers2