Converting tree-like object structure into an array and interating the whole thing

Question

Hi. I have a tree-like object structure that consists of two types of objects:

1. object of class Category
2. object of class CategoryLink

The structure is the following:

The whole story begins with an array of Categories that have no parent Each Category has a few unimportant properties and a few important:
$parent - containing an id of a parent Category,
$children - containin an array of childern Categories (may be empty if the category has no childern of course).
$links - containing an array of CategoryLinks (also possibly empty)

While __constructing a Category, I look for existing child Categories and CategoryLinks, and if there are some, I create their instances and add them to $children and $links, so this procedure repeats for the children and their children and so on, until a category with no children is reached.

So what this procedure does is that it basically creates a tree of Categories and their Links. This goes well enough, until I want to output this tree structure (using Smarty), and I'm not quite sure how to iterate over it the proper way. Desired output is something like this

Parent1 -its unimportant properties
    -Child1 - its unimportant properties
    -Child2 -...
        -Child2's Child1
        -Child2's Child2
    -Child3
Parent2
    -Child1
        -Child1's Child1
    -Child2
Parent3
...

I'm not sure if its better to iterate over it in PHP and convert it to a multi-dimensional array and iterate over it in Smarty, or do it all the way in Smarty.

*note that I didn't mention objects of class CategoryLink, as the Category may contain only one-dimensional array of them, so iterating over them is rather easy, I'm just not sure how to iterate over the whole structure.

What is the best | right way to do this?

Answer 1

Trees lend themselves to very elegant recursive operations. In this case you're describing a depth-first pre-order traversal. The Wikipedia page might be useful. As for the rest, pushing it into a multi-dimensional array sounds sensible enough if that's the easiest way for you to display it.

Answer 2

Even though I'm not an SPL genius, but I think you could do something like this:

Implement RecursiveIterator. And then do:

$iterator = new RecursiveIteratorIterator(
    $theMostTopParent
);
foreach ($iterator as $category) {
     // your code
}

As I said, I never worked with SPL, but I am really sure you can do something like this. So, why not give it a chance?

Nice thing about this: If Smarty has a foreach-loop this will work in smarty, too.