商城的菜单导航需要扩充大类，变成多级菜单。于是建立树形结构是比较好的方法。

一般来说，树形结构有两种方法存储，数组存储和节点指针方式。因为这次是给同事做底层库，菜单分类不多，撑死不会过一千。所以决定用数组方式，特点是快，易理解和调试。指针的调试怎么的也比数组来的难吧！

现有的数据库表里，存有每个分类（node节点）的自身id和上级id。

所以我想做成类似这种添加节点的方式：$tree->setnode(id, parentId, xxx);

于是乎觉得，用数组再合适不过了。

以下方法实现了最基本的树结构，包括添加node，取node值，遍历父节点路径，取儿子集合等等常用操作。可以很方便的扩展成适用自己需求的树，下面会提到。

/*
 * 实现树形结构的基类
 * @author zhengguorui
 */
class Tree {
    // 节点名称
    var $data = array ();
    // 以下三个为实现树结构的数组
    var $child = array (- 1 => array () );    // 节点的儿子
    var $parent = array ();                    // 节点的父亲
    var $layer = array (- 1 => - 1 );         // 节点的深度

    /*
     * 默认根节点为0，其父亲节点为-1
     */
    function Tree($value) {
        $this->setNode ( 0, - 1, $value );
    }

    /* 设置新节点。
     * （自身id，父节点id，名称）
     */
    function setNode($id, $parent, $value) {
        $parent = $parent ? $parent : 0;

        // 存节点名
        $this->data[$id] = $value;
        // 存子节点
        $this->child[$id] = array ();
        // 设置父节点的子为自己
        $this->child[$parent] [] = $id;
        // 设置父节点
        $this->parent [$id] = $parent;
        // 设置节点层级
        if (! isset ( $this->layer [$parent] )) {
            $this->layer [$id] = 0;
        } else {
            $this->layer [$id] = $this->layer [$parent] + 1;
        }
    }

    /*
     * 递归取子节点集合
     */
    function getList(&$tree, $root = 0) {
        foreach ( $this->child[$root] as $key => $id ) {
            // 取root的子节点
            $tree [] = $id;
            // 递归取子节点的子节点
            if ($this->child[$id])
                $this->getList ( $tree, $id );
        }
    }

    /*
     * 返回节点的名称
     */
    function getValue($id) {
        return $this->data[$id];
    }

    /*
     * 返回节点的深度
     */
    function getLayer($id, $space = false) {
        return $space ? str_repeat ( $space, $this->layer [$id] ) : $this->layer [$id];
    }

    /*
     * 返回节点的父亲
     */
    function getParent($id) {
        return $this->parent[$id];
    }

    /*
     * 返回节点的父节点路径，直到root
     */
    function getParents($id) {
        while ( $this->parent[$id] != - 1 ) {
            $id = $parent [$this->layer [$id]] = $this->parent [$id];
        }
        ksort($parent);
        reset($parent);
        return $parent;
    }

    /*
     * 返回直接子节点，仅一层
     */
    function getChild($id) {
        return $this->child[$id];
    }

    /*
     * 返回所有子节点
     */
    function getChilds($id = 0) {
        $child = array ($id );
        $this->getList ( $child, $id );
        return $child;
    }

}

上面是实现基本树结构的方法。但是对于本例中的菜单，每个节点（即分类）除了“名字”这个属性外，还有“该分类拥有的品牌”属性。getParents、getChilds等方法，返回的数组没有直接返回 id->name 这样的数组，实际使用中有些许不便。所以就利用PHP的extends方法重写成适合自己需求的类吧！

/*
 * 菜单树形结构类
 * 增加品牌列表属性
 * 和getset方法
 * @author zhengguorui
 */
class TreeMenu extends Tree{
    // 增加新属性，节点拥有的品类
    var $brands = array ();

    /*
     * 设置某节点的品类
     * （节点id，品类id，品类名称）
     */
    function setBrand($id = 0, $brand_id = -1, $brand_name = "null" ) {
        if( $iddata[$id]) )
            return;
        // 先给自己的 list 新增
        if (! isset ( $this->brands [$id] )) {
            $this->brands [$id] = array();
        }
        if( !isset($this->brands[$id][$brand_id]) ){
            $this->brands[$id][$brand_id] = $brand_name;
        }

        // 然后递归给自己的父节点新增
        self::setBrand( parent::getParent($id), $brand_id, $brand_name);
    }

    /*
     * 返回节点下拥有的品类列表
     */
    function getBrands($id = 0, $isList=false) {
        $origlist = array();
        if( isset($this->brands[$id]) ){
            $origlist = $this->brands[$id];
        }
        return self::brandtoarray($origlist, $isList );
    }

    /*
     * 返回父节点
     */
    function getParent($id, $isList=false) {
        if($id==0){
            return array();
        }
        $origlist = parent::getParent($id);
        return self::idtoarray( array("0"=>$origlist), $isList );
    }

    /*
     * 返回节点的父节点路径，直到root
     */
    function getParents($id, $isList=false) {
        $origlist = parent::getParents($id);
        return self::idtoarray($origlist, $isList );
    }

    /*
     * 返回直接子节点，仅一层
     */
    function getChild($id, $isList=false) {
        $origlist = parent::getChild($id);
        return self::idtoarray( $origlist, $isList );
    }

    /*
     * 返回所有子节点
     */
    function getChilds($id = 0, $isList=false) {
        $origlist = parent::getChilds($id);
        return self::idtoarray($origlist, $isList );
    }

    /*
     * 将 index->id 的数组方式转为 id->name 的方式
     */
    function idtoarray($origlist, $isList=false){
        $newlist = array();
        if(isset($origlist)){
            $newlist = array();
            foreach ( $origlist as $key => $value ) {
                if($isList){
                    array_push($newlist, array(
                        'id'    =>    $value,
                        'name'    =>    self::getValue($value),
                    ));
                }else{
                    $newlist[$value] = self::getValue($value);
                }
            }
        }
        return $newlist;
    }

    /*
     * 将 index->id 的数组方式转为 id->name 的方式
     */
    function brandtoarray($origlist, $isList=false){
        $newlist = array();
        if(isset($origlist)){
            $newlist = array();
            foreach ( $origlist as $key => $value ) {
                if($isList){
                    array_push($newlist, array(
                        'id'    =>    $key,
                        'name'    =>    $value,
                    ));
                }else{
                    $newlist[$key] = $value;
                }
            }
        }
        return $newlist;
    }

}