Implementing a tree

[nospam]

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:
CREATE TABLE tags
(
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?

Thanks!
Pete

[Oli Filth]

nospam said the following on 16/09/2005 18:55:

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:
CREATE TABLE tags
(
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.

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)
{
$flatArray[$node->parentId]->addChild($node);
}
(This example assumes you're using PHP 5).

--
Oli

[Oli Filth]

Oli Filth said the following on 16/09/2005 19:10:

nospam said the following on 16/09/2005 18:55:

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:
CREATE TABLE tags
( 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.
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;

^
Oops, that should be:
$this->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)
{
$flatArray[$node->parentId]->addChild($node);
}
(This example assumes you're using PHP 5).

--
Oli