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/ 5 7816
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
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>
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/
"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
);
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/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Dave |
last post by:
Hello all,
After perusing the Standard, I believe it is true to say that once you
insert an element into a std::list<>, its location in memory never changes.
This makes a std::list<> ideal for...
|
by: Casper |
last post by:
In scanning a drive and comparing file content, I need to remember
filepaths to every single file I encounter so I can take actions on
certain files later on.
Rather than having a huge list...
|
by: prabhat143 |
last post by:
Hi,
Given a singly linked, null terminated list, how can it be converted to
tree? Each node in the list has three attributes: it's ID, it's parent
ID and of course, the next node it's pointing...
|
by: Foodbank |
last post by:
Hi all,
I'm trying to do a binary search and collect some stats from a text
file in order to compare the processing times of this program (binary
searching) versus an old program using linked...
|
by: Ken |
last post by:
I have a binary tree in VB NET and insertions seem to be slow.
The program receives data from one source and inserts it into the tree.
The program receives data from another source and...
|
by: raylopez99 |
last post by:
What's the best way of implementing a multi-node tree in C++? What I'm
trying to do is traverse a tree of possible chess moves given an intial
position (at the root of the tree). Since every...
|
by: Joerg Schoen |
last post by:
Hi folks!
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort...
|
by: Gigs_ |
last post by:
Hi all!
I have text file (english-croatian dictionary) with words in it in alphabetical
order.
This file contains 179999 words in this format:
english word: croatian word
I want to make...
|
by: mac |
last post by:
I found that with memory allocating techniques used nowadays
(addresses alignment, eg. on 32bit machines) one can detect loops in a
tree structure very fast, without using extra memory. This is due...
|
by: erikbower65 |
last post by:
Using CodiumAI's pr-agent is simple and powerful. Follow these steps:
1. Install CodiumAI CLI: Ensure Node.js is installed, then run 'npm install -g codiumai' in the terminal.
2. Connect to...
|
by: linyimin |
last post by:
Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for...
|
by: erikbower65 |
last post by:
Here's a concise step-by-step guide for manually installing IntelliJ IDEA:
1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on...
|
by: kcodez |
last post by:
As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it...
|
by: DJRhino1175 |
last post by:
When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this -
If...
|
by: Rina0 |
last post by:
I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in...
|
by: DJRhino |
last post by:
Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer)
If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _
310030356 Or 310030359 Or 310030362 Or...
|
by: lllomh |
last post by:
Define the method first
this.state = {
buttonBackgroundColor: 'green',
isBlinking: false, // A new status is added to identify whether the button is blinking or not
}
autoStart=()=>{
|
by: Mushico |
last post by:
How to calculate date of retirement from date of birth
| |