当前位置:首页>

文章详细页

无限级分类菜单的实现

分类:算法


 “字符串”拼接的形式
方式一:递归算法

方式二:非递归算法,借助栈的思想

“树状”父子的形式

方式一:递归算法2

方式二:非递归算法2


<?php

/*
无限级分类菜单的实现方式
展示了两种算法:递归算法、非递归算法
展示了两种结果形式:字符串拼接形式、树状结构形式
*/

//源数据
$list = [
  0 =>["cateid" => "1","title" => "家电","parentid" => "0","createtime" => 0],
  1 =>["cateid" => "2","title" => "服装","parentid" => "0","createtime" => 0],
  2 =>["cateid" => "3","title" => "上衣","parentid" => "2","createtime" => 0],
  3 =>["cateid" => "4","title" => "衬衣","parentid" => "3","createtime" => 0],
  4 =>["cateid" => "5","title" => "裤子","parentid" => "2","createtime" => 0],
  5 =>["cateid" => "6","title" => "短裤","parentid" => "5","createtime" => 0],
  6 =>["cateid" => "7","title" => "冰箱","parentid" => "1","createtime" => 0],
  7 =>["cateid" => "8","title" => "食品","parentid" => "0","createtime" => 0]
];


/* ================    “字符串”拼接形式     ================== */

//========== 方式一:获取排序后的分类,递归算法
function getOptions($list,$parentid = 0,$level = 0){
    $arrTree = [];
    if(empty($list)){
        return [];
    }
    $level++;
    foreach($list as $key => $val){
        if($val['parentid'] == $parentid){
            $val['level'] = $level;
            $arrTree[] = $val;
            unset($list[$key]);
            $arrTree = array_merge($arrTree, getOptions($list, $val['cateid'], $level));//找其子类合并
        }
    }

    return $arrTree;
}

//========== 方式二:获取排序后的分类,非递归算法,借助栈的思想
function getOptionsStack($list){
    $list = array_reverse($list);
    $arr = [];
    $temp = [];
    foreach($list as $key=>$val){//先取出所有的顶级分类
        if($val['parentid']==0){
            $val['level'] = 1;
            unset($list[$key]);
            array_push($temp,$val);
        }
    }
    while(count($temp)>0){
        $par = array_pop($temp);//array_pop,然后将其子分类入栈
        $arr[] = $par;
        foreach($list as $key=>$val){
            if($val['parentid']==$par['cateid']){
                $val['level'] = $par['level']+1;
                unset($list[$key]);
                array_push($temp,$val);
            }
        }
    }
    return $arr;
}

//========== 添加前缀 |--- 并且去除多余项
function addPrefix($list,$prefix="|---"){
    $arr = [];
    foreach($list as $val){//将$prefix重复level次,拼接到原title处
        $arr[$val['cateid']] = str_repeat($prefix,$val['level']).$val['title'];
    }
    return $arr;
}

//========== 测试

$order = getOptions($list, 0, 0);//递归算法
$order = getOptionsStack($list);//非递归算法-栈

$final = addPrefix($order,"|---");
echo '<pre>';
print_r($final);
echo '<pre/>';

/*========== 结果
Array
(
    [1] => |---家电
    [7] => |---|---冰箱
    [2] => |---服装
    [3] => |---|---上衣
    [4] => |---|---|---衬衣
    [5] => |---|---裤子
    [6] => |---|---|---短裤
    [8] => |---食品
)
*/



/* ================    “树状”父子形式     ================== */


//无限极分类,递归算法2
function getOptionsAno($list, $root = 0){
    $tree = array();
    foreach($list as $key => $val){

        if($val['parentid'] == $root){
            //获取当前$pid所有子类
                unset($list[$key]);
                if( !empty($list) ){
                    $child = getOptionsAno($list, $val['cateid']);
                    if(!empty($child)){
                        $val['_child'] = $child;
                    }                   
                }              
                $tree[] = $val;
        }
    }   
    return $tree;
}


//无限极分类,非递归算法2
function getOptionsAnother($list, $root = 0){
    // 创建Tree
    $tree = array();
    if(is_array($list)) {
        // 创建基于主键的数组引用
        $refer = array();
        foreach ($list as $key => $data) {
            $refer[$data['cateid']] =& $list[$key];
        }
        foreach ($list as $key => $data) {
            // 判断是否存在parent
            $parentId =  $data['parentid'];
            if ($root == $parentId) {
                $tree[] =& $list[$key];
            }else{
                if (isset($refer[$parentId])) {
                    $parent =& $refer[$parentId];
                    $parent['_child'][] =& $list[$key];
                }
            }
        }
    }
    return $tree;
}



//$order1 = getOptionsAno($list, 0);//递归算法
$order1 = getOptionsAnother($list, 0);//非递归算法
echo '<pre>';
print_r($order1);
echo '<pre/>';


/*========== 结果
Array(
    [0] => Array(
            [cateid] => 1
            [title] => 家电
            [parentid] => 0
            [createtime] => 0
            [_child] => Array(
                    [0] => Array(
                            [cateid] => 7
                            [title] => 冰箱
                            [parentid] => 1
                            [createtime] => 0
                        )
                )
        )
    [1] => Array(
            [cateid] => 2
            [title] => 服装
            [parentid] => 0
            [createtime] => 0
            [_child] => Array(
                    [0] => Array(
                            [cateid] => 3
                            [title] => 上衣
                            [parentid] => 2
                            [createtime] => 0
                            [_child] => Array(
                                    [0] => Array(
                                            [cateid] => 4
                                            [title] => 衬衣
                                            [parentid] => 3
                                            [createtime] => 0
                                        )
                                )
                        )
                    [1] => Array(
                            [cateid] => 5
                            [title] => 裤子
                            [parentid] => 2
                            [createtime] => 0
                            [_child] => Array(
                                    [0] => Array(
                                            [cateid] => 6
                                            [title] => 短裤
                                            [parentid] => 5
                                            [createtime] => 0
                                        )
                                )
                        )
                )
        )
    [2] => Array(
            [cateid] => 8
            [title] => 食品
            [parentid] => 0
            [createtime] => 0
        )
)
*/