[C] Iterator Method for Binary Tree

[Uni Git]

I've been given the following instruction:

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

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

[i]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).[/i]

"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 wonder if anyone could tell me how to start writing this function.

[ZeekyHBomb]

This is easily solved with quite trivial recursion.
Each child-node can be perceived as the root of another tree. If it doesn't have any children itself, well it's just a very small tree.
You want to apply a function to each node-value of a tree. You start by just applying it to the current (root) value and call the iteration-function on each child. There the function will do the same: apply the function to the value at the current node (the "perceived root") and continue down (because everybody knows that trees obviously grow down).

By the way, I remember you making at least two other threads asking programming questions. Are you aware of the [url=http://facepunch.com/showthread.php?t=1250528]WDYNHW[/url]-thread? You can probably post them there and keep the thread-view cleaner.

Also, it seems that you are doing these as exercises for a programming class. It would seem to me that your teacher should be the person you should ask, or perhaps collaborate with some class mates (learning by finding solutions by yourself is so much more satisfying).

[r0b0tsquid]

Read this page and understand it: [url=http://en.wikipedia.org/wiki/Tree_traversal]http://en.wikipedia.org/wiki/Tree_traversal[/url]

Zeeky nailed it pretty much.

It's better to solve these assignments for yourself though, you're not doing them for the instructor, he gets paid whether you pass or fail.

[Uni Git]

[QUOTE=ZeekyHBomb;43415340]This is easily solved with quite trivial recursion.
Each child-node can be perceived as the root of another tree. If it doesn't have any children itself, well it's just a very small tree.
You want to apply a function to each node-value of a tree. You start by just applying it to the current (root) value and call the iteration-function on each child. There the function will do the same: apply the function to the value at the current node (the "perceived root") and continue down (because everybody knows that trees obviously grow down).

By the way, I remember you making at least two other threads asking programming questions. Are you aware of the [url=http://facepunch.com/showthread.php?t=1250528]WDYNHW[/url]-thread? You can probably post them there and keep the thread-view cleaner.

Also, it seems that you are doing these as exercises for a programming class. It would seem to me that your teacher should be the person you should ask, or perhaps collaborate with some class mates (learning by finding solutions by yourself is so much more satisfying).[/QUOTE]

Yeah, sorry, I was looking at other iterator methods for other programs with arrays and also asked on StackOverflow and got incredibly more confused. Thus, I thought I post on here and in a new thread as I thought I'd have to do more explaining or elaborating.

I'm not actually allowed to ask the teacher, and my peers are just as clueless as me! And believe me I've looked everywhere for a solution, it's just hard to get around the concept of tree arrays.

Thanks a lot, anyway!