Hulver's site || Cheese is an Antidepressant

Diaries
Everything
Who's Online?
FAQ / Help

[RFH] Recursion

By veldmon (Thu May 11, 2006 at 06:51:19 AM EST) professor, recursion, depth, breadth, help, communists, communism (all tags)

(Forgive the 2nd post in a day)
My professor says it's possible to do a breadth first tree traversal using the "list of children" approach, but I'm only able to do it with the "next sibling, next child" approach. Could any of you Husians (including communists) assist in completing f2 below? TIA

f1(node)
{
# depth first
list_of_children = node->children

    for child in list_of_children {
        f1(child)
    }
}

f2(node)
{
# breadth first
list_of_children = node->children

???
}

f3(node)
{
    # depth first
    if(node->child) {
        f3(node->child)
    }
    if(node->sibling) {
        f3(node->sibling)
    }
}

f4(node)
{
    # breadth first
    if(node->sibling) {
        f4(node->sibling)
    }
    if(node->child) {
        f4(node->child)
    }
}

< Ask Husi | BBC White season: 'Rivers of Blood' >

Poll

Votes: 2
Results	\|	Other Polls

Related Links

- husi
- veldmon's Diary

Comment Controls

[RFH] Recursion | 9 comments (9 topical, 0 hidden)

I'm not sure how this impacts our customers by georgeha (4.00 / 3) #1 Thu May 11, 2006 at 06:58:50 AM EST

so I can't assign the proper priority to have a developer look into this.

Rates start at by Breaker (4.00 / 2) #2 Thu May 11, 2006 at 07:05:56 AM EST

1000 GBP per day for my time, discount available for > 2 week booking.

Although, for free, if you're having to walk a tree breadth first I'd examine your data model before writing code.

use python! by ucblockhead (4.00 / 4) #3 Thu May 11, 2006 at 07:06:27 AM EST

Then it's trivial!
---
[ucblockhead is] useless and subhuman

In order to understand recursion by DesiredUsername (4.00 / 4) #4 Thu May 11, 2006 at 07:08:15 AM EST

You must first understand recursion

---
Now accepting suggestions for a new sigline

with regard to the poll by lm (4.00 / 2) #5 Thu May 11, 2006 at 07:11:12 AM EST

If matter is finite, all creation necessarily begins with destruction. Consequently, there is no choice but to destroy because material beings must create to exist.

Kindness is an act of rebellion.

: but is it not written by martingale (4.00 / 1) #9 Thu May 11, 2006 at 04:42:37 PM EST

in Lavoisier 3:16
"Rien ne se perd, rien ne se crée, tout se transforme." (Nothing is destroyed and nothing is created, everything transforms).
--
$E(X_t|F_s) = X_s,\quad t > s$
[ Parent ]

breadth first?!?! by TPD (4.00 / 3) #6 Thu May 11, 2006 at 07:28:57 AM EST

But surely it's closer to tea time!

why sit, when you can sit and swivel with The Ab-Swiveller^TM

Your problem is that by ObviousTroll (4.00 / 2) #7 Thu May 11, 2006 at 07:51:34 AM EST

All your functions are missing the "operation" part of the traversal.

Nobody traverses a tree without doing something at each node they visit.

Here's a hint:

visit(node)
{
#Hellllllooooooo Node!

#actual work goes here
}

f1(node)
{
# depth first
list_of_children = node->children

    for child in list_of_children {
      f1(child)
    }

visit(node)
}

A breadth first version of this isn't much more subtle, but it requires handling the "visit" part differently and at a different time.

--
You're no good to me dead. Even half-alive would be socially awkward. - Hugh MacLeod

I don't think your f4 is right by jacob (4.00 / 1) #8 Thu May 11, 2006 at 08:08:37 AM EST

Though you didn't explain exactly how you're representing trees. But I think it will definitely fail for, e.g., a balanced binary tree with height 3.

--

[RFH] Recursion | 9 comments (9 topical, 0 hidden)

-	Yes	50%
-	No	50%


Make a new account
Username:
Password: