Posted by C. (http://symcbean.blogspot.com/) on 10/19/07 21:45

On 19 Oct, 20:06, uidzer0 <ben.lemasur...@gmail.com> 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 |
>
<snip>
>
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7
>

Some relational DBMS provide tree walking SQL extensions (like
Oracle's 'connect by') but they're not portable, and you don't say
what DBMS you use.

You're data already *represents* that structure - just perhaps not in
a very useful way.

Its probably a lot simpler if you do it in PHP code. There are any
number of ways to solve this, but its worth observing that you're code
is probably an over-simplification of the data structure. e.g. you
might go with a right threaded binary tree:

// this is a template of the node structure
$node=array( $current=-1, $next=-1, $first_child=-1,
$payload=array() );
// e.g. 5,4,7, blah
// 7,6,-1,foo
// 6,5,-1,bar
// 4,3,-1,tog
// 3,2,5, zip
// 2,1,3
Which work very nicely when you want to dynamically tinker with the
structure and perform lots of tree walks (hint: use recursive
functions). And they scale really nicely.

Or simply use nested arrays. Do you really need someone to explain how
to code this? Admittedly a single pass algorithm is a little tricky,
but if you can't get your head around a multipass solution, you're
going to be back here a lot asking for help.

C.

[Back to original message]