Representing a tree

So here’s what i’m trying to model in MySQL/PHP.

A Leaf will have exactly 3 ancestors;
Leaf <= Type <= SuperType <= Category
Each category can have multiple SuperTypes, each SuperType can have multiple Types, each Type can have multiple Leaves.

Representing this in the database isnt difficult; parsing it is.
A page will load with a given Category value; I need to retrieve all Leaves that belong to said category; that’s easy.
Now i need to walk the tree in-order. Foreach Supertype…Foreach Type… Foreach Leaf. So i need to determine the best way to establish the database and how to translate it into a walkable tree.

Additional: Leaves have a different data model than any other type (additional values). The other types carry only a Name value.

imho the Nested Set Model is the way to go.

life for me became so much easier once I started using it for the type of application you’re asking about.

if interested I have posted sql scripts to move nodes and their children in this thread

So… how does this model let me walk the tree in a Foreach fashion? I need to be able to wrap tree layers in a div tag…


<div class='Category'>
<div class='SuperType'>SuperTypeName
  <div class='typegroup'>TypeName
    <div class='leafgroup'>
       <a>Leaf1</a><br />
       <a>Leaf2</a><br /> (yes i know this BR is dangling)
<div class='SuperType'>SuperTypeName2
  <div class='typegroup'>TypeName2
    <div class='leafgroup'>
       <a>Leaf3</a><br />
       <a>Leaf4</a><br />

generally what you need to do is

  1. build your categories table structure as described in the tutorial at the other end of the link I posted. the lft and rgt values for each category (node) represent where each category is in the hierarchy are then used to retrieve, move or delete nodes and their children.

  2. assign lft and rgt values to each category as described in the tutorial.

  3. build an sql query to retrieve the categories you need to display in the browser.

  4. generate the html as you loop through the retrieved categories from 3).

That… told me all of nothing.
“How do I make this walkable?”
“Make it walkable.”

simply Looping through the elements doesnt work - you dont get a chance to close tags from 6 elements ago, unless i’m missing something.
If i have to loop through the elements and put them into a tree inside PHP, what precisely have i accomplished by redesigning my table? I have no need to search within the tree itself - the full tree (each Category being a tree) will be pulled every time.

well, I’m not going to write the sql and php code for you.

post some code so I can see you are making an attempt to work it out for yourself and I can then try to help you.

I’m not into spoon feeding - well not for free at least :wink:

otherwise I can’t help anymore and so hopefully someone else will come along to help you.

It’s a Kalon post, you’ll get used to it (or put him on ignore).

Trees are simply arrays with nested arrays. The PHP array will look something like this

$episodes => array (
  0 => array (
    'title' => 'Broken Arm',
    'date' => '12/1/10',
    'claims' => array (
      0 => array (
        'insurer' => 'Payee',
        'dateFiled' => '12/3/10',
        'procedures' => array (
          0 => array (
            'name' => 'Set Arm',
            'charge' => '100.00'

Traversing the array will look like this (using braceless syntax and short tags here).

<? foreach ( $episodes as $episode ): ?>
  <div class="episode">
    <h2><?= $episode['title'] ?></h2>
      <? foreach ( $episode['claims'] as $claim ): ?>
        <li><?= $claim['payee'] ?>
            <? foreach ($claim['procedures'] as $procedure): ?>
              <li><?= $procedure['name'] ?></li>
            <? endforeach ?>
      <? endforeach ?>
<? endforeach ?>

Pretty simple really. Assembling the starting array above is the trickiest part, the traversal is pretty straightforward.

assembling the array is reasonably straight forward as well if I use the nested set model.

but I would just use the rows in the result set returned from the db queries and not bother transferring them to an array.

once you get your head around what the lft and rgt values represent and the concept behind them, life should become very much easier (it did for me).