Algorithm for creating a tree structure from a linked list

Jeffrey Silverman

Hi, all. I have a linked list. I need an algorithm to create a tree
structure from that list.

Basically, I want to turn this:

$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);

Into this (or something similar):

$tree =
array('A' => array('value' => 'aaa',
'B' => array ('value' => 'bbb',
'C' => array('value'=>'ccc')
),
'D' => array ('value' => 'ddd')
);

I have tried and agonized for ages over this but my pea brain
cannot get it.

As an alternative, a tree may not be necessary. I am using the linked
list to create a "site map". If anyone can suggest a method to take the
linked list and directly create a nested layout (using HTML <UL> and <LI>
tags), that would be spectacular!

(Also, if the $list from the above example is not technically a "linked
list", please do not freak out and focus on that. It is close enough.
Please, please, please, tell me what is, if it is not a "linked list")

Thanks!!

--
Jeffrey D. Silverman | jeffrey AT jhu DOT edu
Website | http://www.wse.jhu.edu/newtnotes/

Jul 17 '05 #1

David Rybach

Jeffrey Silverman wrote:

Hi, all. I have a linked list. I need an algorithm to create a tree
structure from that list.

Basically, I want to turn this:

$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);

Into this (or something similar):

$tree =
array('A' => array('value' => 'aaa',
'B' => array ('value' => 'bbb',
'C' => array('value'=>'ccc')
),
'D' => array ('value' => 'ddd')
);

I have tried and agonized for ages over this but my pea brain
cannot get it.

As an alternative, a tree may not be necessary. I am using the linked
list to create a "site map". If anyone can suggest a method to take the
linked list and directly create a nested layout (using HTML <UL> and <LI>
tags), that would be spectacular!

(Also, if the $list from the above example is not technically a "linked
list", please do not freak out and focus on that. It is close enough.
Please, please, please, tell me what is, if it is not a "linked list")

Thanks!!

Hi,

perhaps you want to try this:

// Your list
$aList = array(
array('id'=>'A','parent'=>0,'val'=>'aa'),
array('id'=>'B','parent'=>'A','val'=>'bb'),
array('id'=>'C','parent'=>'A','val'=>'cc'),
array('id'=>'D','parent'=>'B','val'=>'dd'),
array('id'=>'E','parent'=>'C','val'=>'ee'),
array('id'=>'F','parent'=>'E','val'=>'ff')
);

// Transform datastructure
$sons = array();
$nodes = array();
foreach($aList as $i => $node) {
if($node['parent'] === 0)
$root = $node['id'];
else
// Get List of sons per node
$sons[$node['parent']][] = $node['id'];
// Build array with ids as keys
// Better get this as input
$nodes[$node['id']] =
array('parent'=>$node['parent'],'val'=>$node['val']);
}

// Build Sidemap
function sitemap($id, &$nodes, &$sons)
{
$retval = '<li>'.$nodes[$id]['val'];
if(is_array($sons[$id])) {
$retval .= '<ul>';
foreach($sons[$id] as $son) {
$retval .= sitemap($son, $nodes, $sons);
}
$retval .= '</ul>';
}
$retval .= '</li>';
return $retval;
}
echo '<ul>';
echo sitemap($root, $nodes, $sons);
echo '</ul>';
It's surely not the best and not the fastest solution, but it works.

By the way, your $list is not a linked list. It is an array, i.e. an array
of associative arrays. Linked lists have only sequential access.

Regards,
David

Jul 17 '05 #2

Andy Hassall

On Tue, 17 Feb 2004 11:38:09 -0500, Jeffrey Silverman <je*****@jhu.edu> wrote:

Hi, all. I have a linked list. I need an algorithm to create a tree
structure from that list.

Basically, I want to turn this:

$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);

Into this (or something similar):

$tree =
array('A' => array('value' => 'aaa',
'B' => array ('value' => 'bbb',
'C' => array('value'=>'ccc')
),
'D' => array ('value' => 'ddd')
);

I have tried and agonized for ages over this but my pea brain
cannot get it.

<pre>
<?php
$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);
$tree = array();
$nodes = array();

foreach ($list as $node) {
$nodes[$node['id']] = array('value' => $node['value']);

if (is_null($node['parent_id']))
$tree[$node['id']] = &$nodes[$node['id']];
else
{
if (!isset($nodes[$node['parent_id']]))
$nodes[$node['parent_id']] = array();
$nodes[$node['parent_id']][$node['id']] = &$nodes[$node['id']];
}
}

print_r($tree);
?>
</pre>

Output:

Array
(
[A] => Array
(
[value] => aaa
[b] => Array
(
[value] => bbb
[C] => Array
(
[value] => ccc
)

)

[D] => Array
(
[value] => ddd
)

)

)

--
Andy Hassall <an**@andyh.co.uk> / Space: disk usage analysis tool
<http://www.andyh.co.uk> / <http://www.andyhsoftware.co.uk/space>

Jul 17 '05 #3

Jeffrey Silverman

On Tue, 17 Feb 2004 20:13:48 +0100, David Rybach wrote:

By the way, your $list is not a linked list. It is an array, i.e. an array
of associative arrays. Linked lists have only sequential access.

Thank you (and you, too, AH).

But in the sense that each branch in the $list array "knows" which branch
is its parent, is that a linked list?

later...

--
Jeffrey D. Silverman | jeffrey AT jhu DOT edu
Website | http://www.wse.jhu.edu/newtnotes/

Jul 17 '05 #4

Hugh Bothwell

"Jeffrey Silverman" <je*****@jhu.edu> wrote in message
news:pa****************************@jhu.edu...

Hi, all. I have a linked list. I need an algorithm to create a tree
structure from that list.

Basically, I want to turn this:

$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);

Into this (or something similar):

$tree =
array('A' => array('value' => 'aaa',
'B' => array ('value' => 'bbb',
'C' => array('value'=>'ccc')
),
'D' => array ('value' => 'ddd')
);
(Also, if the $list from the above example is not technically a "linked
list", please do not freak out and focus on that. It is close enough.
Please, please, please, tell me what is, if it is not a "linked list")
In a linked list, each item keeps a reference to the
next item in the list (the 'link'); there is no way of
going directly to a given item. Offhand I'd just call
this an array of records. As you say, not super-important.
How's this?

// Arbitrary value for tree root-node ID;
// must not collide with other ids
define('ROOTNAME', 'root');

// Field-name constants
define('IDNAME', 'id');
define('PARENTNAME', 'parent_id');
define('CHILDREN','children');

// Use the most generic method, or the fastest?
define(SAFEMODE, true);
// Return an empty tree
function init_tree() {
return array(
ROOTNAME => array(
CHILDREN => array()
)
);
}
// Add node to tree
// Expects a tree, the (index => values) for a node,
// and the node's parent-id
// Returns success as boolean
// N.B. tree is passed by reference
function insert_child(&$tree, $parent, $index, $values) {
if ($parent === null)
$parent = ROOTNAME;

if (!isset($tree[$parent]))
{
// Can't find parent! No way to add to tree
return false;
}
else
{
// insert new leaf
$tree[$index] = $values; // N.B. index must be unique!
$tree[$index][CHILDREN] = array();

// link back to parent node
$tree[$parent][CHILDREN][] = $index;

// inserted successfully
return true;
}
}
// Add list of child-nodes to tree
// For each child-node, if the parent-node is
// not already in the tree, that insertion will fail.
// Children that are not successfully inserted are
// returned in the list.
// N.B. tree and list are passed by reference
function insert_list(&$tree, &$list) {
foreach($list as $key => $values)
{
$parent = $values[PARENTNAME];
unset($values[PARENTNAME];

$index = $values[IDNAME];
unset($values[IDNAME]);

if (insert_child($tree, $parent, $index, $values))
{
// Insertion was successful! Remove child from list.
unset($list[$key]);
}
}
}
// Build a tree from a list of nodes.
// Returns the fullest possible tree;
// children who do not belong to the tree
// remain in the list.
// N.B. list is passed by reference
function build_tree(&$list) {
$tree = init_tree();

if (SAFEMODE)
{
$numItems = count($list);

do
{
$old_numItems = $numItems;

insert_list($tree, $list);

$numItems = count($list);
}
while (
// Repeat until list is empty or no more inserts are possible
($numItems > 0) && ($numItems < $old_numItems)
);
}
else
{
/*
* This only works if you can GUARANTEE that
* all parent nodes will appear in the list before
* their children.
*/
insert_list($tree, $list);
}

return $tree;
}
As an alternative, a tree may not be necessary. I am using the linked
list to create a "site map". If anyone can suggest a method to take the
linked list and directly create a nested layout (using HTML <UL> and <LI>
tags), that would be spectacular!

// Return values as formatted string
// MODIFY THIS AS DESIRED
function printfValues($values) {
return "".$values['value'];
}

// Return the formatted list as a string
function format_tree($in, $out, $start, $end, $tree, $id) {
if ( count($tree[$id][CHILDREN]) > 0 )
{
$str = $in;
foreach($tree[$id][CHILDREN] as $childID)
$str .=
$start
.printfValues($tree[$childID])
.format_tree($in, $out, $start, $end, $tree, $childID)
.$end;
$str .= $out;

return $str;
}
else
return '';
}
and - TA-DA! - finally:

echo format_tree(
'<ul>', '</ul>', '<li>', '</li>', build_tree($list), ROOTNAME
);

Jul 17 '05 #5

malcolm

I use this snip to make menus. I hope you can get some ideas from it.

while( $item = each($list) ) {
print "<strong>{$item[0]}</strong><br>\n";
while( $subitem = each($item[1]) ) {
print "<a href=\"{$subitem[1]}\">{$subitem[0]}</a><br>\n";
On Tue, 17 Feb 2004 11:38:09 -0500, Jeffrey Silverman <je*****@jhu.edu>
wrote:

Hi, all. I have a linked list. I need an algorithm to create a tree
structure from that list.

Basically, I want to turn this:

$list = array(
array( 'id' => 'A', 'parent_id' => null, 'value' => 'aaa')
, array( 'id' => 'B', 'parent_id' => 'A', 'value' => 'bbb')
, array( 'id' => 'C', 'parent_id' => 'B', 'value' => 'ccc')
, array( 'id' => 'D', 'parent_id' => 'A', 'value' => 'ddd')
);

Into this (or something similar):

$tree =
array('A' => array('value' => 'aaa',
'B' => array ('value' => 'bbb',
'C' => array('value'=>'ccc')
),
'D' => array ('value' => 'ddd')
);

I have tried and agonized for ages over this but my pea brain
cannot get it.

As an alternative, a tree may not be necessary. I am using the linked
list to create a "site map". If anyone can suggest a method to take the
linked list and directly create a nested layout (using HTML <UL> and <LI>
tags), that would be spectacular!

(Also, if the $list from the above example is not technically a "linked
list", please do not freak out and focus on that. It is close enough.
Please, please, please, tell me what is, if it is not a "linked list")

Thanks!!

--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

Jul 17 '05 #6