Iterator Method for Binary Trees in C

Question

1.00/5 (1 vote)

See more:

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.)

C

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:

C

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!

Edit: 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 test 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));

Posted 5-Jan-14 14:33pm

MikeBah

Updated 6-Jan-14 1:17am

v2

Add a Solution

Comments

Richard MacCutchan 6-Jan-14 5:00am

quite a few errors (such as "from pointer without a cast").
Is it really that difficult to copy and paste the exact error message(s) and also indicate which line they refer to?

2 solutions

Solution 2

C++

bst_char_iterate(t, fun);         // what type is t?
bst_char_iterate(t, *fun);        // *fun is incorrect, use fun
bst_char_iterate(t->root, fun);   // what type is root?
bst_char_iterate(t, fun(c));      // fun(c) is wrong, use fun

And in all the above cases what is fun and where is it defined?

As I said in my first comment, you need to show the exact error message the compiler produces.

Posted 6-Jan-14 2:40am

Richard MacCutchan

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2014-01-06T01:31:00

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

Keeping it simple:

C

// the dumbest monotonic function...
char  my_fun(char c)
{
  return c;
}


int main()
{
  bst_char * ptree;
  // ...
  // ... create the tree, make ptree pointing to it
  // ...
  bst_char_iterate(ptree, my_fun);
  // ...
  // ... free the tree
  // ...
  return 0;
}