PHP - help with recursion

feenster99 · 16 Feb 2006 at 21:36

Hi folks,
I think this is an easy one, but its the first time I have attempted recursion.

I have a MySQL table that stores items for a menu. It has the following fields:
- id
- depth
- left_id
- right_id
- title

So I have entered the data (manually at the moment, but will be automated eventually), and they look like this when selected into an array:

Code:

Array
(
    [0] => Array
        (
            [id] => 1
            [depth] => 0
            [left_id] => 0
            [right_id] => 2
            [title] => Home
        )

    [1] => Array
        (
            [id] => 2
            [depth] => 0
            [left_id] => 1
            [right_id] => 4
            [title] => News
        )

    [2] => Array
        (
            [id] => 4
            [depth] => 1
            [left_id] => 2
            [right_id] => 5
            [title] => Archive
        )

    [3] => Array
        (
            [id] => 5
            [depth] => 2
            [left_id] => 4
            [right_id] => 3
            [title] => Really old stuff
        )

    [4] => Array
        (
            [id] => 3
            [depth] => 0
            [left_id] => 5
            [right_id] => 0
            [title] => Contact us
        )
)

This should produce a menu structure of:

Code:

- Home
- News
-- Archive
--- Really old stuff
- Contact us

Can anyone create a simple recursive function to generate that structure from the above array?

Cheers,
Matt

feenster99 · 16 Feb 2006 at 21:58

Because there is no specified limit to the depth the menu could go. It could be 2 levels deep or it could be 20

Matt

feenster99 · 16 Feb 2006 at 22:36

jamesrw said:
I'm not sure the whole left_id, right_id thing is the correct way to go about it? Why not try having a parent / child thing going on?

Yeah, im not sure it offers anything either to be honest - was something new I was trying. However, I don't see that having a parent_id offers me a great advantage though to be honest. The problem is that when iterating through the array, it doesn't know whether an ID has children or not. It goes something like this:

- look at item
- add to array
- move to next item
- does item have a parent?
- if yes - Damn, go back a step and add it to the children list!
- if no - Move onto the next

I wonder if I would be better doing the sorting from the end of the array and working upwards? That way, I would know if an item had a parent, so could pass its ID onto the next iteration of the loop to be attached to its parent.

Blimey this hurts my head :S

DJ_Jestar - thanks for the code. The problem is, your array is already sorted into a parent/children relationship - thats the stage I am trying to get to.

Cheers,
Matt

feenster99 · 16 Feb 2006 at 22:51

What sort of table structure would you suggest for a parent/child menu then? I think this left_id and depth stuff is heading in the wrong direction.

Any suggestions?

Matt

feenster99 · 16 Feb 2006 at 23:42

Thanks again - that is great, but I need them in an array which is what is causing me such trouble. E.g., I need this as my output, which I don't think is doable with your code:

Code:

array(
	[0] = array(	"id"	=> "1",
			"title" => "Home",
			"depth" => "0",
			"parent"=> "0");

	[1] = array(	"id"	=> "2",
			"title" => "News",
			"depth" => "0",
			"parent"=> "0",
			"children" =>
				[2] = array(	"id"	=> "3",
						"title" => "Archive",
						"depth" => "1",
						"parent"=> "2");
		);

)