Iterator Method for Binary Trees in C

[MikeBah]

I've been given the following instruction:

Add a new method to the library that applies a function to every value in the tree. (This is an iterator method for trees.)

int bst_char_iterate(bst_char *t, char (*fun)(char item))

NB: The BST property will only be preserved by this method if the function passed to it is monotonic. A function f is monotonic whenever
x <= y (arrow) f(x) <= f(y).

"Bst_char t" equating to a pointer to the tree, "fun" equating to a pointer to a function call and "item" being the value of which the function is called upon.

I've managed to come up with this:

int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
    assert(t!=NULL);
    struct node * p = t->root;
    if (p!=NULL) {
       p->item = fun(p->item);
       p->left->item = bst_char_iterate(t,fun(p->left));
       p->right->item = bst_char_iterate(t,fun(p->right));
    } else {
       return 0;
    }
}

This cannot compile, with quite a few errors (such as "from pointer without a cast").

Please help!

[L7Sqr]

In general, a binary tree container is recursive. That is, the internal members are also of type binary tree. Example:

typedef struct bst_ {
   char payload;
   struct bst_ *left, *right;
} bst_type;

It seems that you are trying to access the root of the tree explicitly (via struct node *p = t->root). I'm not sure how this works unless you provide the structure definition for bst_char. Also, it is usually helpful for us if you provide the error output you are getting - we don't have access to your code and any little bit of info helps.

My hunch is that you should instead be doing something like:

void bst_char_iterate (bst_char *root, char (*fun)(char item)) {
   if (! root) { return; }
   root->item = fun (root->item);
   bst_char_iterate (root->left, fun);
   bst_char_iterate (root->right, fun)
}

I changed the return type to void since I'm not sure what it should be used for in this case.

N.B. I've taken liberties without seeing your assignment or definitions of your structures. The more information you provide the more this advice can be adjusted to match your true problems.

[MikeBah]

I have managed to get it to compile with this code:

int bst_iterate(struct node *p, char (*fun)(char item)) {
    if (p!=NULL) {
       p->item = fun(p->item);
       bst_iterate(p->left,fun);
       bst_iterate(p->right,fun);
    } else {
       return 0;
    }
}

int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
    assert(t!=NULL);
    bst_iterate(t->root,(fun));
}

But I've no idea how to implement it in the program.

I've tried:

bst_char_iterate(t, fun);
bst_char_iterate(t, *fun);
bst_char_iterate(t->root, fun);
bst_char_iterate(t, fun(c));

[deceptikon]

This article may be helpful. It describes both recursive traversal and an iterator based design.

But I've no idea how to implement it in the program.

You mean calling the function? Your first example should work, provided fun is defined and t is a pointer to bst_char. Another variation would be this:

char print(char item)
{
    putchar(item);
}

int main(void)
{
    bst_char tree;

    // Build the tree...

    bst_char_iterate(&tree, print);

    // Destroy the tree...

    return 0;
}

[MikeBah]

Thank you very much, it just worked with:

bst_char_iterate(tree, print);

[anas.man]

try this :

void bst_char_apply(bst_char *t, void (*fun)(char item)) {
    if (t->left) bst_char_apply(t->left, fun);
    fun(t->value);
    if (t->right) bst_char_apply(t->right, fun);
}