#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    3
    Rep Power
    0

    Exclamation Iterator Method for Binary Trees in C


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

    Code:
    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:

    Code:
    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!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    > p->left->item = bst_char_iterate(t,fun(p->left));
    > p->right->item = bst_char_iterate(t,fun(p->right));
    These should be
    bst_char_iterate(p->left,fun);
    bst_char_iterate(p->right,fun);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    3
    Rep Power
    0
    Originally Posted by salem
    > p->left->item = bst_char_iterate(t,fun(p->left));
    > p->right->item = bst_char_iterate(t,fun(p->right));
    These should be
    bst_char_iterate(p->left,fun);
    bst_char_iterate(p->right,fun);
    When I changed it, the following errors came up when attempting to compile:

    pfbst_char.c: In function ‘bst_char_iterate’:
    pfbst_char.c:388:8: warning: passing argument 1 of ‘bst_char_iterate’ from incompatible pointer type [enabled by default]
    bst_char_iterate(p->left,fun);
    ^
    pfbst_char.c:381:5: note: expected ‘struct bst_char *’ but argument is of type ‘struct node *’
    int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
    ^
    pfbst_char.c:389:8: warning: passing argument 1 of ‘bst_char_iterate’ from incompatible pointer type [enabled by default]
    bst_char_iterate(p->right,fun);
    ^
    pfbst_char.c:381:5: note: expected ‘struct bst_char *’ but argument is of type ‘struct node *’
    int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
    ^
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    3
    Rep Power
    0
    I have managed to get it to compile with this code:

    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:

    Code:
    bst_char_iterate(t, fun);
    bst_char_iterate(t, *fun);
    bst_char_iterate(t->root, fun);
    bst_char_iterate(t, fun(c));
  8. #5
  9. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    Well first you need to write a function you want to call for each node on the tree.

    Say
    Code:
    char printit(char item) {
      putchar(item);
    }
    Then
    bst_char_iterate(t, printit);
    should do the biz.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo