tree iterations c++

Question

Looking for examples on simple tree iterations in C++, both recursive and iterative. (post, pre and in-order)

Answer 1

This page shows an example of a binary tree and how to iterate over it.

Answer 2

The Adobe Source Library's adobe::forest<T> is a generic tree container that can be iterated post- pre- or in-order. The documentation has examples of how to accomplish these different types of iterations.

Answer 3

if your tree looks like this:

struct Node{
    Node *left, *right, *parent;

    int value; // or some other important data :-)
}

then this is how you make a recursive in-order iteration:

void iterate(Node *n){
    if(!n)
        return;

    iterate(n->left);
    cout << n->value; // do something with the value
    iterate(n->right);
}

If you swap the lines with n->left and n->right the tree will be iterated in reverse order.

These are the pre-order and post-order iterations:

void iterate_pre(Node *n){
    if(!n)
        return;

    cout << n->value; // do something with the value
    iterate_pre(n->left);
    iterate_pre(n->right);
}

void iterate_post(Node *n){
    if(!n)
        return;

    iterate_post(n->left);
    iterate_post(n->right);
    cout << n->value; // do something with the value
}

The non-recursive iteration is a little bit more complicated. First thing you need is to find a first node in the tree (like vector<T>::begin())

Node *find_first(Node *tree){
    Node *tmp;
    while(tree){
        tmp = tree;
        tree = tree->left
    }
    return tmp;
}

Then you need a way to get the next item of the tree (vector<T>::iterator::operator++()).

Node *next(Node *n){
    assert(n);

    if(n->right)
        return find_first(n->right)

    while(n->parent && n->parent->right == n)
        n = n->parent;

    if(!n->parent)
        return NULL;

    return n;
}

(this function tries to find a first node in the right subtree and if it's not possible, goes up the tree until the path comes from the right subtree)