Adjacency tree from single table

Question

I've read a lot of people discussing nested lists, but I was wondering how to iterate through an adjacancy list/tree in PHP.

I have a table with: id, title, parent_id

And I've selected all records out into an array called $pages.

Then using this php:

function makeList($pages, $used) {
    if (count($pages)) {
        echo "<ul>";
        foreach ($pages as $page) {
            echo "<li>".$page['pag_title'];
            $par_id = $page['pag_id'];
            $subsql("SELECT * FROM pages WHERE pag_parent = ".$par_id."");

            // running the new sql through an abstraction layer
            $childpages = $dbch->fetchAll();
            makeList($childpages, $used, $lastused);
            echo "</li>";
        }
        echo "</ul>";
    }
}

This sort of works but I end up with any sub menu being repeated e.g.

• Home
  • News
    • Sub-news
  • Articles
    • Article
• News
  • Sub-news
• Articles
  • Article
• Sub-news
• Article

I've tried adding the current id into an array that gets passed through the function, and then using in_array to check if it's there, but I have had no joy doing that.

Any help would be much appreciated.

I need to parse the whole tree so choosing parent as 0 isn't an option

Answer 1

Since it already does the SQL, you dont have to do it outside before the first function call.

function makeList($par_id = 0) {
    //your sql code here
    $subsql("SELECT * FROM pages WHERE pag_parent = $par_id");
    $pages = $dbch->fetchAll();

    if (count($pages)) {
        echo '<ul>';
        foreach ($pages as $page) {
            echo '<li>', $page['pag_title'];
            makeList($page['pag_id']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

For storing it more tree like you might want to look at this site: Storing Hierarchical Data in a Database.

Answer 2

If you create an array of pages grouped by parent id it is quite easy to recursively build the list. This will only require one database query.

<?php

 //example data
 $items = array(
    array('id'=>1, 'title'=>'Home', 'parent_id'=>0),
    array('id'=>2, 'title'=>'News', 'parent_id'=>1),
    array('id'=>3, 'title'=>'Sub News', 'parent_id'=>2),
    array('id'=>4, 'title'=>'Articles', 'parent_id'=>0),
    array('id'=>5, 'title'=>'Article', 'parent_id'=>4),
    array('id'=>6, 'title'=>'Article2', 'parent_id'=>4)
 );

 //create new list grouped by parent id
 $itemsByParent = array();
 foreach ($items as $item) {
    if (!isset($itemsByParent[$item['parent_id']])) {
        $itemsByParent[$item['parent_id']] = array();
    }

    $itemsByParent[$item['parent_id']][] = $item;
 }

 //print list recursively 
 function printList($items, $parentId = 0) {
    echo '<ul>';
    foreach ($items[$parentId] as $item) {
        echo '<li>';
        echo $item['title'];
        $curId = $item['id'];
        //if there are children
        if (!empty($items[$curId])) {
            makeList($items, $curId);
        }           
        echo '</li>';
    }
    echo '</ul>';
 }

printList($itemsByParent);