Implementing a tree

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
Hi all,

I'd like to implement a tree of "tags" for a blog I'm writing for fun in PHP.
Here's what a single tag looks like:

      name      varchar(30) not null default '',
      id_self   integer(12) not null primary key,
      id_parent integer(10) not null default 0,
   INSERT INTO tags VALUES ('root of the tree', 0, 0);

Each tag has a name, a unique id to identify itself with and a parent's id,
and all this will be stored in a database, but stored in no particular order.

I'm a little stumped as to how to reconstruct the tree.  Part of the problem
is that suppose my first read to the database yeilds:

   name = "physics"
   id_self = 21
   id_parent = 2

but further down in the database, this record exists:

   name = "science"
   id_self = 2
   id_parent = 0

in other words, it's possible that children may be read before parents.  

I've noticed that some people have implemented a tree class.  Since this is
supposed to be a *fun* project for me, I'd rather write it myself.  But I
find myself staring at the keyboard, not knowing how to start.

How can I reconstruct this tree?


Re: Implementing a tree

nospam said the following on 16/09/2005 18:55:
Quoted text here. Click to load it

One simple way round this would be to load each tree element into a flat  
array at first, each element keyed by its own ID.  Then loop through  
every element in turn, get its parent's ID, and then call an addChild()  
function or something, e.g:

class Node
    public $id;
    public $parentId;
    public $children;

    public function addChild($childObject)
        $children[$childObject->id] = $childObject;

// assume that $flatArray is the array of unconnected Nodes that have
// been constructed from the database query.

foreach ($node in $flatArray)

(This example assumes you're using PHP 5).


Re: Implementing a tree

Oli Filth said the following on 16/09/2005 19:10:
Quoted text here. Click to load it
Oops, that should be:
    $this->children[$childObject->id] = $childObject;
Quoted text here. Click to load it


Site Timeline