A very common situation in web development is the category tree, in its nature , its just a recursive traversal of a tree data structure. This post will demonstrate the method of generating a tree while traversing the data strucute.

Step 1. Create a database table to store the category data:

 
CREATE TABLE `category` (
  `id` INT(11) NOT NULL AUTO_INCREMENT,
  `short_name` VARCHAR(100) COLLATE utf8_unicode_ci NOT NULL DEFAULT '',
  `show_name` VARCHAR(100) COLLATE utf8_unicode_ci NOT NULL DEFAULT '',
  `parent_id` INT(11) NOT NULL DEFAULT 0,
  `keywords` VARCHAR(1000) COLLATE utf8_unicode_ci NOT NULL DEFAULT '',
  `desc` VARCHAR(1000) COLLATE utf8_unicode_ci NOT NULL DEFAULT '',
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
 
 
 

Let's add some data into it:

 
INSERT INTO category VALUES ('','fruit','Fruit',0,'','');
INSERT INTO category VALUES ('','apple','Apple',11,'','');
INSERT INTO category VALUES ('','orange','Orange',11,'','');
INSERT INTO category VALUES ('','banana','Banana',11,'','');
 
INSERT INTO category VALUES ('','book','Book',0,'','');
INSERT INTO category VALUES ('','cooking_book','Cooking Book',15,'','');
INSERT INTO category VALUES ('','computer_book','Computer Book',15,'','');
 

The category may be output as all kinds of forms like drop down selection menu, sidebar category tree, breadcrumb. So we use a class to represent the category data model and provide different service through the method of the class.

 
<?php
class CategoryModel {
 
    private $cat_tree = NULL;/* tree data structure */
    private $nodes = array();/* tree node array */
    private $records = NULL;/* data from database*/
?>
 

The first thing the class should do is load data from database:

 
    public function __construct() {
        $this->InitTree();
    }
 
    public function InitTree() {
 
        if($this->records != NULL) return;
 
        $this->records = d()->querysql("select * from category");
 
        foreach($this->records as &$i) {
            $this->nodes[] = array('data' => &$i, 'childs' => array() , 'parent' => NULL);
        }
 
        $this->cat_tree = array('data' => NULL, 'childs' => array() , 'parent' => NULL); // root
        foreach($this->nodes as &$i) {
            if($i['data']->parent_id == 0 ) { 
                $this->cat_tree['childs'][] = &$i;
                $i['parent'] = &$this->cat_tree; 
                $i['childs'] = $this->Recursive($i);                
            }
        }
 
    }
 
 
    public function Recursive(&$parent) {
        $childs = array();
 
        foreach($this->nodes as &$i) {
            if($i['data']->parent_id == $parent['data']->id) {
                $childs[] = &$i;
                $i['parent'] = &$parent;
                $i['childs'] = $this->Recursive($i);
            }
        }
 
        return $childs;
    }
 
 

After running of initTree, we will get this tree data structure:

 
Array
(
    [data] => 
    [childs] => Array
        (
            [0] => Array
                (
                    [data] => stdClass Object
                        (
                            [id] => 11
                            [short_name] => fruit
                            [show_name] => Fruit
                            [parent_id] => 0
                            [keywords] => 
                            [desc] => 
                        )
 
                    [childs] => Array
                        (
                            [0] => Array
                                (
                                    [data] => stdClass Object
                                        (
                                            [id] => 12
                                            [short_name] => apple
                                            [show_name] => Apple
                                            [parent_id] => 11
                                            [keywords] => 
                                            [desc] => 
                                        )
 
                                    [childs] => Array
                                        (
                                        )
 
                                    [parent] => Array
 *RECURSION*
                                )
 
                            [1] => Array
                                (
                                    [data] => stdClass Object
                                        (
                                            [id] => 13
                                            [short_name] => orange
                                            [show_name] => Orange
                                            [parent_id] => 11
                                            [keywords] => 
                                            [desc] => 
                                        )
 
                                    [childs] => Array
                                        (
                                        )
 
                                    [parent] => Array
 *RECURSION*
                                )
 
                            [2] => Array
                                (
                                    [data] => stdClass Object
                                        (
                                            [id] => 14
                                            [short_name] => banana
                                            [show_name] => Banana
                                            [parent_id] => 11
                                            [keywords] => 
                                            [desc] => 
                                        )
 
                                    [childs] => Array
                                        (
                                        )
 
                                    [parent] => Array
 *RECURSION*
                                )
 
                        )
 
                    [parent] => Array
                        (
                            [data] => 
                            [childs] => Array
 *RECURSION*
                            [parent] => 
                        )
 
                )
 
            [1] => Array
                (
                    [data] => stdClass Object
                        (
                            [id] => 15
                            [short_name] => book
                            [show_name] => Book
                            [parent_id] => 0
                            [keywords] => 
                            [desc] => 
                        )
 
                    [childs] => Array
                        (
                            [0] => Array
                                (
                                    [data] => stdClass Object
                                        (
                                            [id] => 16
                                            [short_name] => cooking_book
                                            [show_name] => Cooking Book
                                            [parent_id] => 15
                                            [keywords] => 
                                            [desc] => 
                                        )
 
                                    [childs] => Array
                                        (
                                        )
 
                                    [parent] => Array
 *RECURSION*
                                )
 
                            [1] => Array
                                (
                                    [data] => stdClass Object
                                        (
                                            [id] => 17
                                            [short_name] => computer_book
                                            [show_name] => Computer Book
                                            [parent_id] => 15
                                            [keywords] => 
                                            [desc] => 
                                        )
 
                                    [childs] => Array
                                        (
                                        )
 
                                    [parent] => Array
 *RECURSION*
                                )
 
                        )
 
                    [parent] => Array
                        (
                            [data] => 
                            [childs] => Array
 *RECURSION*
                            [parent] => 
                        )
 
                )
 
        )
 
    [parent] => 
)
 
 

To generate HTML code of the tree, we have to traverse the tree and output some HTML tags at some special point of the process of traversing. For example, when enter into a subdirectory we may add a ul tag and close the tag when leave the subdirectory. How to do this? We use callback function:

 
    public function DepthTravel(&$root, $d, $callback , $foreachBeforeEvent = NULL, $foreachAfterEvent = NULL , $beforeRecursiveEvent = NULL , $afterRecursiveEvent = NULL) {
 
        if($root['parent'] !== NULL) {
            $this->$callback($root, $d);
        }
 
        if ( count ( $root['childs'] ) > 0 && $foreachBeforeEvent != NULL) {
            $this->$foreachBeforeEvent ( $root , $d );
        }
 
        foreach($root['childs'] as &$c) {
            if ($beforeRecursiveEvent != NULL) $this->$beforeRecursiveEvent( $root , $d );
            $this->DepthTravel($c, $d+1, $callback , $foreachBeforeEvent , $foreachAfterEvent , $beforeRecursiveEvent  , $afterRecursiveEvent );
            if ($afterRecursiveEvent != NULL) $this->$afterRecursiveEvent( $root , $d );
        }
 
        if ( count ( $root['childs'] ) > 0 && $foreachAfterEvent != NULL) {
            $this->$foreachAfterEvent ( $root , $d );
        }
 
    }
 

The traversal function accept 5 callback function. They will get called at special point of the traversing. The 'callback', get called when encounter any node that is not the root node, the root node is a dummy node, don't contain any data.

For example, we want to output a selection list with indentation according to the depth of the tree:

 
    public function OutputSelect($selected = 0 ) {
 
        $this->selected = $selected;
 
        ?>
        <select name="cat">
        <?php
 
        $this->DepthTravel($this->cat_tree, 0, 'select');
 
        ?>
        </select>
        <?php
 
    }
 
    public function select(&$node , $d) {
 
        echo '<option ';
        if($this->selected === $node['data']->short_name ) echo 'selected="selected" ';
        echo ' value="' . $node['data']->short_name . '">';
        for($i = 0 ; $i < ($d -1 ) * 4 ; $i++)
            echo ' ';
        echo   $node['data']->show_name . "</option>" ;
    }
 
 

The output will be:

By providing different callback function , the traversing will generate different HTML code:

 
    public function OutputSidebarNav() {
        $this->DepthTravel( $this->cat_tree , 0 , 'li','foreachLiBeforeEventSidebar' , 'foreachLiAfterEvent', 'liBeforeRecursiveEvent' , 'liAfterRecursiveEvent');
    }
 
    public function li( &$node , $d ) {
 
        echo '<a'; 
 
        if( $d == 1 ) 
            echo ' class="top" ';
 
        echo ' href="/cat/'.$node['data']->short_name.'" >'.$node['data']->show_name; 
 
        echo '</a>';
 
    }
 
    public function liBeforeRecursiveEvent ( &$node , $d ) {
 
        for($i = 0 ; $i < ($d  ) * 4 ; $i++)
            echo ' ';
        echo '<li' ; 
 
        if( $d == 0 ) 
            echo ' class="top"';
 
        echo ' >';
    }
 
    public function liAfterRecursiveEvent ( &$node , $d ) {
        for($i = 0 ; $i < ($d  ) * 4 ; $i++)
            echo ' ';
        echo '</li>' . "\n";
    }
 
 
    public function foreachLiBeforeEventSidebar(&$node , $d) {
 
        echo "\n" ;
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '<ul ';
 
        echo '>' . "\n";
    }
    public function foreachLiBeforeEvent(&$node , $d) {
 
        echo "\n" ;
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '<ul ';
 
        if (  $node['data'] == NULL) {
            echo 'class="top first"';
        }
 
        echo '>' . "\n";
    }
 
    public function foreachLiAfterEvent(&$node , $d) {
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '</ul>' . "\n";
    }
 

The entire code

 
<?php
include('class.dsn.php');
 
function d() {
    static $d = NULL;
    if( $d == NULL) {
        $d = new DSN();
    } 
    return $d;
}
 
class CategoryModel {
 
    private $cat_tree = NULL;/* tree data structure */
    private $nodes = array();/* tree node array */
    private $records = NULL;/* data from database*/
 
    public function __construct() {
        $this->InitTree();
        print_r($this->cat_tree);
    }
 
    public function InitTree() {
 
        if($this->records != NULL) return;
 
        $this->records = d()->querysql("select * from category");
 
        foreach($this->records as &$i) {
            $this->nodes[] = array('data' => &$i, 'childs' => array() , 'parent' => NULL);
        }
 
        $this->cat_tree = array('data' => NULL, 'childs' => array() , 'parent' => NULL); // root
        foreach($this->nodes as &$i) {
            if($i['data']->parent_id == 0 ) { 
                $this->cat_tree['childs'][] = &$i;
                $i['parent'] = &$this->cat_tree; 
                $i['childs'] = $this->Recursive($i);                
            }
        }
 
    }
 
 
    public function Recursive(&$parent) {
        $childs = array();
 
        foreach($this->nodes as &$i) {
            if($i['data']->parent_id == $parent['data']->id) {
                $childs[] = &$i;
                $i['parent'] = &$parent;
                $i['childs'] = $this->Recursive($i);
            }
        }
 
        return $childs;
    }
 
 
    public function select(&$node , $d) {
 
        echo '<option ';
        if($this->selected === $node['data']->short_name ) echo 'selected="selected" ';
        echo ' value="' . $node['data']->short_name . '">';
        for($i = 0 ; $i < ($d -1 ) * 4 ; $i++)
            echo ' ';
        echo   $node['data']->show_name . "</option>" ;
    }
 
    public function OutputSelect($selected = 0 ) {
 
        $this->selected = $selected;
 
        ?>
        <select name="cat">
        <?php
 
        $this->DepthTravel($this->cat_tree, 0, 'select');
 
        ?>
        </select>
        <?php
 
    }
 
    public function DepthTravel(&$root, $d, $callback , $foreachBeforeEvent = NULL, $foreachAfterEvent = NULL , $beforeRecursiveEvent = NULL , $afterRecursiveEvent = NULL) {
 
        if($root['parent'] !== NULL) {
 
            $this->$callback($root, $d);
        }
 
        if ( count ( $root['childs'] ) > 0 && $foreachBeforeEvent != NULL) {
            $this->$foreachBeforeEvent ( $root , $d );
        }
 
        foreach($root['childs'] as &$c) {
            if ($beforeRecursiveEvent != NULL) $this->$beforeRecursiveEvent( $root , $d );
            $this->DepthTravel($c, $d+1, $callback , $foreachBeforeEvent , $foreachAfterEvent , $beforeRecursiveEvent  , $afterRecursiveEvent );
            if ($afterRecursiveEvent != NULL) $this->$afterRecursiveEvent( $root , $d );
        }
 
        if ( count ( $root['childs'] ) > 0 && $foreachAfterEvent != NULL) {
            $this->$foreachAfterEvent ( $root , $d );
        }
 
    }
 
    public function OutputSidebarNav() {
        $this->DepthTravel( $this->cat_tree , 0 , 'li','foreachLiBeforeEventSidebar' , 'foreachLiAfterEvent', 'liBeforeRecursiveEvent' , 'liAfterRecursiveEvent');
    }
 
    public function li( &$node , $d ) {
 
        echo '<a'; 
 
        if( $d == 1 ) 
            echo ' class="top" ';
 
        echo ' href="/cat/'.$node['data']->short_name.'" >'.$node['data']->show_name; 
 
        echo '</a>';
 
    }
 
    public function liBeforeRecursiveEvent ( &$node , $d ) {
 
        for($i = 0 ; $i < ($d  ) * 4 ; $i++)
            echo ' ';
        echo '<li' ; 
 
        if( $d == 0 ) 
            echo ' class="top"';
 
        echo ' >';
    }
 
    public function liAfterRecursiveEvent ( &$node , $d ) {
        for($i = 0 ; $i < ($d  ) * 4 ; $i++)
            echo ' ';
        echo '</li>' . "\n";
    }
 
 
    public function foreachLiBeforeEventSidebar(&$node , $d) {
 
        echo "\n" ;
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '<ul ';
 
        echo '>' . "\n";
    }
    public function foreachLiBeforeEvent(&$node , $d) {
 
        echo "\n" ;
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '<ul ';
 
        if (  $node['data'] == NULL) {
            echo 'class="top first"';
        }
 
        echo '>' . "\n";
    }
 
    public function foreachLiAfterEvent(&$node , $d) {
        for($i = 0 ; $i < ($d  ) * 4 - 2 ; $i++)
            echo ' ';
        echo '</ul>' . "\n";
    }
 
}
 
$c = new CategoryModel();
$c->OutputSelect();
$c->OutputSidebarNav();
?>
 

And the class DSN is a simple wrapper of mysql api, you can find it here :

Using php record visitor information