How to write a function to get a tree structured output

Question

I have a table called login. In this i have 3 columns id, name and ref. people can register in the site with reference of another people. Adminhave no reference so the ref value is 0. A & c comes under admin so their ref value is 1. B,D and G comes under A so their ref value is 2. E and F comes under B And a person can refer max of 3 people. . i need to get the out put in a table like this

Whenever you want to work with hierarchical data, you need to add additional informations about the hierarchy with the data. You could take a look at [order sql tree hierarchy](http://stackoverflow.com/questions/14890204/order-sql-tree-hierarchy/14959883#14959883), there are some techniques described. — t.niese, Aug 13 '16 at 10:25

Manjeet Barnala · Accepted Answer · 2016-09-08T09:17:33.770

Use this code get the desired output

<?php 
$connection = mysqli_connect('localhost', 'root', '', 'db_mani'); //connection

$sql = "SELECT * FROM users";
$result = mysqli_query($connection, $sql);
$usersArray = array();
if(mysqli_num_rows($result) > 0){
    while($row = mysqli_fetch_assoc($result)) {
        $usersArray[]= $row; ///will create array of users
    }
}           

function makeMenu($items, $parentId) //will create array in tree structure
{
    $menu = array_filter($items, function ($item) use ($parentId) {
        return     $item['ref'] == $parentId;
    });
    foreach ($menu as &$item) 
    {
        $subItems = makeMenu($items, $item['id']);
        if (!empty($subItems)) 
        {
            $item['child'] = $subItems;
        }
    }
    return $menu;
}

function print_users($usersArray,$ref = 'Admin')
{   
    $str ='<table border="1" width ="300" style="text-align:center;"><tr>';
    foreach($usersArray as $user)
    { 
        $str.='<td>'.$user['name'].' (Ref:'.$ref.')';
        if(!empty($user['child']))
        {
            $str.= print_users($user['child'],$user['name']);
        }
        $str.='</td>';
    }
    $str.='</tr></table>';
    return $str;      
}


$usersArray = makeMenu($usersArray,0); ///call with parent id 0 for first time, this will give usres in tree structure
echo print_users($usersArray); // print users
?>

Final Result :

Database Structure:

I hope this will solve your problem. Thank you.

`makeMenu` iterates on every user in each call thats overkill — cske, Sep 14 '16 at 06:48

cske · Answer 2 · 2016-09-14T06:51:59.397

Improvements based on @Manjeet Barnala's answer, his makeMenu function iterates every node (calling array_filter) for each parent lookup, that coud be done with single loop. A bit simplification in printer function too.

<?php
/**
*/
error_reporting(E_ALL);
ini_set('display_errors',1);


if (false) { //Test data
$usersArray = [
     1 => ['name'=>'Admin','ref'=>0,'childs'=>[]]
   , 2 => ['name'=>'A','ref'=>1,'childs'=>[]]
   , 3 => ['name'=>'b','ref'=>2,'childs'=>[]]
   , 4 => ['name'=>'c','ref'=>1,'childs'=>[]]
   , 5 => ['name'=>'d','ref'=>4,'childs'=>[]]
   , 6 => ['name'=>'e','ref'=>2,'childs'=>[]]
   , 7 => ['name'=>'f','ref'=>2,'childs'=>[]]
   , 8 => ['name'=>'g','ref'=>4,'childs'=>[]]
   , 9 => ['name'=>'h','ref'=>4,'childs'=>[]]
];
    }
else {
    $connection = mysqli_connect('localhost', 'root', '', 'db_mani'); //connection

    $sql = "SELECT * FROM users";
    $result = mysqli_query($connection, $sql);
    $usersArray = array();
    if(mysqli_num_rows($result) > 0){
        while($row = mysqli_fetch_assoc($result)) {
            $row['childs'] = [];
            $usersArray[$row['id']]= $row; ///will create array of users
        }
    }

}
$roots = [];
foreach ($usersArray as $id => &$user) {
    if ( empty($user['ref']) ) {
        //empty parent mean's i'm a root node
        $roots[] = $id;
    }
    else {
        //uplink user to it's parents childs array
        $usersArray[$user['ref']]['childs'][] = $id;
    }
}

$htmlTableForm = function ($userId) use (&$usersArray,&$htmlTableForm) {
    $childs = count($usersArray[$userId]['childs']);
    $parent = $usersArray[$userId]['ref'];
    $text   = $usersArray[$userId]['name'] . ( 0 < $parent ? ('('.$usersArray[$parent]['name'].')') :'');
    if ( 1 > $childs) {
        return  $text;
    }
    $tblCode  = ['<table><tr ><td colspan="'.$childs.'">',$text,'</td></tr><tr>'];
    foreach($usersArray[$userId]['childs'] as $childId){
        $tblCode[] = '<td>'.$htmlTableForm($childId).'</td>';
    }
    $tblCode[] ='</tr></table>';
    return implode('',$tblCode);
};

//Question unclear about multiple roots goes into same table or separated , even possilbe to exists, so this is the simpliest case
echo $htmlTableForm($roots[0]);

score 1 · Answer 3 · answered Sep 07 '16 at 12:55

Just create a array refs containing just a Zero (ref of Admin) and a empty array tree. Then use a while loop as long refs not empty and query all persons with ref equals the first element of the array refs. After this query you remove the first element of refs. Put all queried presons with the ref as key into the tree. Add also all persons id into the refs array. This way you build up the tree.

The next step is to visualize the tree. Simply write a helper fnction countAllChildren($node) to count ... all the children of a node by recursion. This hleper function is needed to calculate the colspan of your td's.Now you have to walk the tree from root to top/leaf and print every person (dnt forget the colspan calculated by countAllChildren($node))

I hope this will give you the drive into the right direction. Have fun while coding :)

score 0 · Answer 4 · answered Sep 14 '16 at 11:19

The idea is to make a two dimensional array. The difficulty is to handle the colspan, because you need to move to the correct row to write your cell. This code seems to work but it's not tested against every situation:

<?php

class Leaf {
    var $name;
    var $ref;
    var $depth;
    var $numChildren;

    var $i;
    function __construct($name, $ref) {
        $this->name = $name;
        $this->ref = $ref;
        $this->numChildren = 0;
    }

}

class Tree {
    var $arrayLeaves;
    var $refLeaves;
    var $matrix;
    var $maxRows;
    var $maxCols;

    function __construct() {
        $this->arrayLeaves = array ();
        $this->refLeaves = array ();
        $this->maxRows = 0;
        $this->maxCols = 0;
    }
    function addLeaf($id, $name, $ref) {
        $leaf = new Leaf ( $name, $ref );
        $this->arrayLeaves [$id] = $leaf;
        if (! isset ( $this->refLeaves [$ref] )) {
            $this->refLeaves [$ref] = array ();
        }
        if (isset ( $this->arrayLeaves [$ref] )) {
            $parent = $this->arrayLeaves [$ref];
            if (null != $parent) {
                $leaf->depth = $parent->depth + 1;
                $parent->numChildren ++;
            } else {
                $leaf->depth = 0;
            }
            if (($leaf->depth + 1) > $this->maxRows) {
                $this->maxRows = $leaf->depth + 1;
            }
        } else {
            $leaf->depth = 0;
            $this->maxRows = 1;

        }
        $this->refLeaves [$ref] [] = $id;
    }
    function colSpan($ind, $leaf) {
        $retval = 0;
        if ($leaf->numChildren == 0) {
            $retval = 1;
        } else {
            $retval = 0;
            foreach ( $this->refLeaves [$ind] as $ref ) {
                $retval += $this->colSpan ( $ref, $this->arrayLeaves [$ref] );
            }
        }
        return $retval;
    }
    function printLeaf($ind, $colId, $parent) {
        $leaf = $this->arrayLeaves [$ind];
        if (null != $leaf) {
            if (null == $parent) {
                $refName = "none";
            } else {
                $refName = $parent->name;
            }
            while ($this->matrix[$leaf->depth] [$colId] != "<td></td>")  { // unsure about that
                $colId++;
            }
            $colspan = $this->colSpan ( $ind, $leaf );
            $this->matrix [$leaf->depth] [$colId] = "<td colspan=\"" . $colspan . "\">{$leaf->name} (ref: $refName)</td>";
            for($i = $colId + 1; $i < ($colId + $colspan); $i ++) {
                $this->matrix [$leaf->depth] [$i] = ""; // remove <td></td>
            }
            for($col = 0; $col < count ( $this->refLeaves [$ind] ); $col ++) {
                $ref = $this->refLeaves [$ind] [$col];
                $this->printLeaf ( $ref, $col, $leaf );
            }
        }
    }


    function printLeaves() {
        $this->matrix = array ();
        $this->maxCols = $this->colSpan(0, $this->arrayLeaves [1]); 
        for($i = 0; $i < $this->maxRows; $i ++) {
            $this->matrix [$i] = array ();
            for($j = 0; $j < $this->maxCols; $j ++) {
                $this->matrix [$i] [$j] = "<td></td>";
            }
        }
        $this->printLeaf ( 1, 0, null );
        echo '<table border="1">';
        for($i = 0; $i < $this->maxRows; $i ++) {
            echo "<tr>";
            for($j = 0; $j < $this->maxCols; $j ++) {
                echo $this->matrix [$i] [$j];
            }
            echo "</tr>";
        }
        echo "</table>";
    }
}
?>
<html>
<head>
</head>
<body>
<?php
$tree = new Tree ();
$tree->addLeaf ( 1, 'admin', 0 );
$tree->addLeaf ( 2, 'A', 1 );
$tree->addLeaf ( 3, 'B', 2 );
$tree->addLeaf ( 4, 'C', 1 );
$tree->addLeaf ( 5, 'D', 2 );
$tree->addLeaf ( 6, 'E', 3 );
$tree->addLeaf ( 7, 'F', 3 );
$tree->addLeaf ( 8, 'G', 2 );

$tree->printLeaves ();

?>
</body>
</html>

score -1 · Answer 5 · answered Sep 07 '16 at 14:06

// Fetch data from BD
// $options = $stmt->query("SELECT * FROM Options")->fetch_all(PDO::FETCH_ASSOC);

$nodes = array();
$roots = array();

// init nodes indexed by IDs
foreach ($options as $option) {
    $option['subIds'] = array(); // init subIds
    $nodes[$option['id']] = $option;
}

// build a recursive structure (by reference)
foreach ($options as $option) {
    if ($option['ref'] == 0) {
        $roots[] = $option['id']; // add a root
    } else {
        $nodes[$option['ref']]['subIds'][] = $option['id']; // add a subnode
    }
}

// build recursive HTML-List
function getSubtreeHTMLList($subOptionIds, $nodes) {
    $result = '<ul>';
    foreach ($subOptionIds as $optionsId) {
        $result .= '<li>';
        $result .= $nodes[$optionsId]['option_name'];
        if (count($nodes[$optionsId]['subIds'] > 0)) {
            $result .= getSubtreeHTMLList($nodes[$optionsId]['subIds'], $nodes);
        }
        $result .= '</li>';
    }
    $result .= '</ul>';
    return $result;
}

echo getSubtreeHTMLList($roots, $nodes);

Result will be something like:

admin
- A
  - B
    - E
    - F
  - D
  - G
- C

Demo

Not like this i need to get ouput exactly what i have mentioned in my post — Juice, Sep 07 '16 at 14:12
Then rewrite the output function. Add a function to count all the children and use this for your `colspan`. Use https://en.wikipedia.org/wiki/Breadth-first_search for processing the tree. PS: we aren't your code monkeys. — Marcus, Sep 08 '16 at 04:37
@Glufu To produce the above out put is easy and the format of the output is important point this question. To form a table with correct col span is difficult. i tried a lot but didn't get the desired output that's why i posted in stack overflow and started bounty. — Juice, Sep 16 '16 at 05:41

How to write a function to get a tree structured output

5 Answers5