Custom iterator on a tree structure in c++

Question

I am implementing a tree structure in c++ with a node class like this:

class Node {
protected:
    // relations
    Node *_parent;
    std::vector<Node*> _children;

public:
    // some example method 
    void someMethod(Node *node) {

        // do something with *node

        for (int i = 0; i < node->_children; i++) {
            _children[i]->myFunction;
        }
    }
}

Now, to work on the nodes in my tree I am implementing recursive functions like someMethod in my example.

It works, but I end up writing the same recursion code over and over again for every new function that works on my tree.

Is there a generic way to iterate a tree structure like I would on a plain array? Some method that returns the next object, until I'm done with the whole branch.

EDIT:

Thanks to everybody who has commented so far, with your help I could narrow down the problem. From my understanding (I'm new to c++), I need an iterator class that encapsulates the code for traversing my tree.

Accessing all tree members should be as simple as that:

for (Node<Node*>::iterator it = _node.begin(); it != _node.end(); ++it) {
    Node *node = *it;
    // do something with *node
}

Now the question is:

How do I implement such an iterator?

how do you return `largestSoFar` and what is the problem exactly? — ogzd, Feb 10 '13 at 14:15
you may want to look this too : http://stackoverflow.com/questions/8961605/algorithm-for-creating-iterator-for-binarytree-class — M3taSpl0it, Feb 10 '13 at 14:32
@M3taSpl0it: My tree is not binary, each node may have n children. — de., Feb 10 '13 at 16:18

score 1 · Answer 1 · answered Feb 10 '13 at 14:22

1

Pass a function pointer to the recursive function that returns the node that you are seeking.

This is the power of function pointers and function pointer arrays in C/C++.

answered Feb 10 '13 at 14:22

Srikant Krishna

881
6
11

Yes, right. I omitted that in my example. I am actually looking for a more generic alternative to the recursive approach. I have edited my question. – de. Feb 10 '13 at 16:35

score 0 · Answer 2 · answered Feb 10 '13 at 14:29

Many function do not simply iterate over all nodes, if the tree is (normally) sorted, then to find the largest value you will only look in the right subtree.

If you search the minimum it is in the left most subtree.

Therefore not always it makes sense, to have an iterator that iterates the whole tree.
But if you need exactly to iterate over all nodes, you can use function pointers, or the Visitor Pattern (Erich Gamma, Design Patterns).

I want to iterate all nodes like I would in a plain array. – de. Feb 10 '13 at 16:38 — de., Feb 10 '13 at 16:38

Custom iterator on a tree structure in c++

2 Answers2