Posted by The Natural Philosopher on 10/19/07 22:22

uidzer0 wrote:
> Hey everyone,
>
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database which looks like this:
>
> Code:
>
> parent_id | child_id |
> ----------------+-------------+
> 1 | 2 |
> 2 | 3 |
> 3 | 4 |
> 3 | 5 |
> 5 | 6 |
> 5 | 7 |
>
>
> So coming out of the database, I get an array which looks like this:
>
> Code:
>
> Array
> (
> [0] => Array
> (
> [parent_id] => 1
> [child_id] => 2
> )
>
> [1] => Array
> (
> [parent_id] => 2
> [child_id] => 3
> )
>
> [2] => Array
> (
> [parent_id] => 3
> [child_id] => 4
> )
> ...
>
>
> I would like to put this into an array which represents the following
> structure:
>
> Code:
>
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7
>
>
> Can anyone point me in the right direction? Let me know if this isn't
> clear - I can try to elaborate.
>
> Thanks!
>
> Ben
>


Try a recursive call to the database..

Thats how I at least got a picture of such a tree structure for my
application. I didn't load it into an array at all.

basically there is a subroutine that takes the parent ID as parameter,
and finds all its children.

For each child, it calls itself with the child as the new parent.

This essentially walks down each branch to a end node and then tries the
next branch.

I love recursion. It makes a fine way to solve a maze.

If you had the data into an array, you wouldn't need a SQL call per
node: In practice it wasn't actually a huge overhead for me.


thats how to walk the tree. To represent it? well I didn't need it
represented in a memory structure, - my tree is like a list of headings
and subheadings, and all I wanted was a table of contents printed out.
Wasn't that hard to do.

I'd say that making a memory structure analogous to the database
structure is the only way to get a one-to-many node going.

Which begs the question of why duplicate that in memory, when its in the
database already, and likely as not cached in memory!

In other words, you have the correct representation already What you may
be lacking is a smart way to walk that tree.

In pseudo code mine goes like this

function walk tree(parent)
FOR I=0 , I less than SIZEOF (total array), I++
DO
if array[i].parent eq parent
THEN walk tree (array[i].child);
DONE
ENDFUNCTION

Or in Mysql type speak
WALK TREE: Parent_id
SELECT * from TREE where PARENT=parent_id ORDER by (whatever);
FOR EACH ROW
WALK TREE(CHILD);
END
END (WALK TREE)

[Back to original message]