PHP实现无限级分类（不使用递归）-php教程-PHP中文網

首頁

後端開發

php教程

PHP实现无限级分类（不使用递归）

PHP中文网

Jun 06, 2016 pm 07:41 PM

在进行无限极分类中最常用的算法就是“递归”，熟悉PHP语言的朋友肯定知道，PHP不擅长递归 ,而且递归次数有限（100次左右，因操作系统和配置而异）。

所以本文将会给大家带来几种不使用递归实现无限级分类的代码。供大家来学习使用。

第一种：

无限级分类在开发中经常使用，例如：部门结构、文章分类。无限级分类的难点在于“输出”和“查询”，例如

将文章分类输出为

查找分类A下面所有分类包含的文章。

1.实现原理
几种常见的实现方法，各有利弊。其中“改进前序遍历树”数据结构，便于输出和查询，但是在移动分类和常规理解上有些复杂。

2.数据结构

<?php
 $list = array(
 array(&#39;id&#39;=>1, &#39;fid&#39;=>0, &#39;title&#39; => &#39;中国&#39;), 
 array(&#39;id&#39;=>2, &#39;fid&#39;=>1, &#39;title&#39; => &#39;江苏&#39;),
 array(&#39;id&#39;=>3, &#39;fid&#39;=>1, &#39;title&#39; => &#39;安徽&#39;),
 array(&#39;id&#39;=>4, &#39;fid&#39;=>8, &#39;title&#39; => &#39;江阴&#39;),
 array(&#39;id&#39;=>5, &#39;fid&#39;=>3, &#39;title&#39; => &#39;芜湖&#39;),
 array(&#39;id&#39;=>6, &#39;fid&#39;=>3, &#39;title&#39; => &#39;合肥&#39;),
 array(&#39;id&#39;=>7, &#39;fid&#39;=>3, &#39;title&#39; => &#39;蚌埠&#39;),
 array(&#39;id&#39;=>8, &#39;fid&#39;=>8, &#39;title&#39; => &#39;无锡&#39;)
 );
?>

登入後複製

由于所有的递归均可以使用循环实现，本文根据PHP语言特点编写了一套关于“无限级”分类的函数，相比递归实现而言效率更高。

3.输出ul列表形式
将上述数据输出为下面的HTML

<ul>
 <li class="first-child">
 <p>江苏</p>
 <ul>
 <li class="first-child last-child">
 <p>无锡</p>
 <ul>
 <li class="first-child last-child">
 <p>江阴</p>
 </li>
 </ul>
 </li>
 </ul>
 </li>
 <li class="last-child">
 <p>安徽</p>
 <ul>
 <li class="first-child"><p>芜湖</p></li>
 <li><p>合肥</p></li>
 <li class="last-child"><p>蚌埠</p></li>
 </ul>
 </li>
</ul>

登入後複製

这种HTML结构在前端使用（使用JavaScript和CSS构造可折叠树）十分方便。具体实现程序如下：

<ul><?php echo get_tree_ul($list, 1); ?></ul>

登入後複製

4.输出option列表形式

<select>
 <option value="2">江苏</option>
 <option value="8">    无锡</option>
 <option value="4">        江阴</option>
 <option value="3">安徽</option>
 <option value="5">    芜湖</option>
 <option value="6">    合肥</option>
 <option value="7">    蚌埠</option>
</select>

登入後複製

具体实现程序如下：

<select>
<?php
 // get_tree_option()返回数组，并为每个元素增加了“深度”（即depth）列，直接输出即可
 $options = get_tree_option($list, 1);
 foreach($options as $op) {
 echo &#39;<option value="&#39; . $op[&#39;id&#39;] .&#39;">&#39; . str_repeat(" ", $op[&#39;depth&#39;] * 4) . $op[&#39;title&#39;] . &#39;<;/option>&#39;;
 }
?>
<;/select>

登入後複製

5. 查找某一分类的所有子类

<?php
 $children = get_tree_child($list, 0);
 echo implode(&#39;,&#39;, $children); // 输出：1,3,2,7,6,5,8,4
?>

登入後複製

6. 查找某一分类的所有父类

<?php
 $children = get_tree_parent($list, 4);
 echo implode(&#39;,&#39;, $children); //8, 2, 10
?>

登入後複製

7. 相关函数

<?php
function get_tree_child($data, $fid) {
 $result = array();
 $fids = array($fid);
 do {
 $cids = array();
 $flag = false;
 foreach($fids as $fid) {
 for($i = count($data) - 1; $i >=0 ; $i--) {
 $node = $data[$i];
 if($node[&#39;fid&#39;] == $fid) {
 array_splice($data, $i , 1);
 $result[] = $node[&#39;id&#39;];
 $cids[] = $node[&#39;id&#39;];
 $flag = true;
 }
 }
 }
 $fids = $cids;
 } while($flag === true);
 return $result;
}
 function get_tree_parent($data, $id) {
 $result = array();
 $obj = array();
 foreach($data as $node) {
 $obj[$node[&#39;id&#39;]] = $node;
 }
  $value = isset($obj[$id]) ? $obj[$id] : null;
 while($value) {
 $id = null;
 foreach($data as $node) {
 if($node[&#39;id&#39;] == $value[&#39;fid&#39;]) {
 $id = $node[&#39;id&#39;];
 $result[] = $node[&#39;id&#39;];
 break;
 }
 }
 if($id === null) {
 $result[] = $value[&#39;fid&#39;];
 }
 $value = isset($obj[$id]) ? $obj[$id] : null;
 }
 unset($obj);
 return $result;
}
 function get_tree_ul($data, $fid) {
 $stack = array($fid);
 $child = array();
 $added_left = array();
 $added_right= array();
 $html_left = array();
 $html_right = array();
 $obj = array();
 $loop = 0;
 foreach($data as $node) {
 $pid = $node[&#39;fid&#39;];
 if(!isset($child[$pid])) {
 $child[$pid] = array();
 }
 array_push($child[$pid], $node[&#39;id&#39;]);
 $obj[$node[&#39;id&#39;]] = $node;
 }
  while (count($stack) > 0) {
 $id = $stack[0];
 $flag = false;
 $node = isset($obj[$id]) ? $obj[$id] : null;
 if (isset($child[$id])) {
 $cids = $child[$id];
 $length = count($cids);
 for($i = $length - 1; $i >= 0; $i--) {
 array_unshift($stack, $cids[$i]);
 }
 $obj[$cids[$length - 1]][&#39;isLastChild&#39;] = true;
 $obj[$cids[0]][&#39;isFirstChild&#39;] = true;
 $flag = true;
 }
 if ($id != $fid && $node && !isset($added_left[$id])) {
 if(isset($node[&#39;isFirstChild&#39;]) && isset($node[&#39;isLastChild&#39;])) {
 $html_left[] = &#39;<li class="first-child last-child">&#39;;
 } else if(isset($node[&#39;isFirstChild&#39;])) {
 $html_left[] = &#39;<li class="first-child">&#39;;
 } else if(isset($node[&#39;isLastChild&#39;])) {
 $html_left[] = &#39;<li class="last-child">&#39;;
 } else {
 $html_left[] = &#39;<li>&#39;;
 }
 $html_left[] = ($flag === true) ? "<p>{$node[&#39;title&#39;]}</p><ul>" : "<p>{$node[&#39;title&#39;]}</p>";
 $added_left[$id] = true;
 }
 if ($id != $fid && $node && !isset($added_right[$id])) {
 $html_right[] = ($flag === true) ? &#39;</ul></li>&#39; : &#39;</li>&#39;;
 $added_right[$id] = true;
 }
  if ($flag == false) {
 if($node) {
 $cids = $child[$node[&#39;fid&#39;]];
 for ($i = count($cids) - 1; $i >= 0; $i--) {
 if ($cids[$i] == $id) {
 array_splice($child[$node[&#39;fid&#39;]], $i, 1);
 break;
 }
 }
 if(count($child[$node[&#39;fid&#39;]]) == 0) {
 $child[$node[&#39;fid&#39;]] = null;
 }
 }
 array_push($html_left, array_pop($html_right));
 array_shift($stack);
 }
 $loop++;
 if($loop > 5000) return $html_left;
 }
 unset($child);
 unset($obj);
 return implode(&#39;&#39;, $html_left);
}
 function get_tree_option($data, $fid) {
 $stack = array($fid);
 $child = array();
 $added = array();
 $options = array();
 $obj = array();
 $loop = 0;
 $depth = -1;
 foreach($data as $node) {
 $pid = $node[&#39;fid&#39;];
 if(!isset($child[$pid])) {
 $child[$pid] = array();
 }
 array_push($child[$pid], $node[&#39;id&#39;]);
 $obj[$node[&#39;id&#39;]] = $node;
 }
  while (count($stack) > 0) {
 $id = $stack[0];
 $flag = false;
 $node = isset($obj[$id]) ? $obj[$id] : null;
 if (isset($child[$id])) {
 for($i = count($child[$id]) - 1; $i >= 0; $i--) {
 array_unshift($stack, $child[$id][$i]);
 }
 $flag = true;
 }
 if ($id != $fid && $node && !isset($added[$id])) {
 $node[&#39;depth&#39;] = $depth;
 $options[] = $node;
 $added[$id] = true;
 }
 if($flag == true){
 $depth++;
 } else {
 if($node) {
 for ($i = count($child[$node[&#39;fid&#39;]]) - 1; $i >= 0; $i--) {
 if ($child[$node[&#39;fid&#39;]][$i] == $id) {
 array_splice($child[$node[&#39;fid&#39;]], $i, 1);
 break;
 }
 }
 if(count($child[$node[&#39;fid&#39;]]) == 0) {
 $child[$node[&#39;fid&#39;]] = null;
 $depth--;
 }
 }
 array_shift($stack);
 }
 $loop++;
 if($loop > 5000) return $options;
 }
 unset($child);
 unset($obj);
 return $options;
}
?>

登入後複製

第二种：

这是使用TP来制作的无限级分类。

算法复杂度为T(n)=O(2n),只遍历两次数组.

关键代码其实只有一行

$return[$v[&#39;pid&#39;]][&#39;child&#39;][$v[&#39;id&#39;]] = &$return[$k];

登入後複製

但是为了实现较为复杂的扩展,这里添加一些额外的信息

//索引要和ID一致,这不是废话么
//pid是父元素
//不要出现死循环嵌套,就是AB互为父子
//不要出现相同name


$list[0]=[&#39;id&#39;=>0,&#39;pid&#39;=>-1,&#39;name&#39;=>&#39;A@0&#39;];//-1用于后面的根目录判断
$list[1]=[&#39;id&#39;=>1,&#39;pid&#39;=>0,&#39;name&#39;=>&#39;A@1&#39;];
$list[2]=[&#39;id&#39;=>2,&#39;pid&#39;=>0,&#39;name&#39;=>&#39;A@2&#39;];
$list[3]=[&#39;id&#39;=>3,&#39;pid&#39;=>2,&#39;name&#39;=>&#39;A@3&#39;];
$list[4]=[&#39;id&#39;=>4,&#39;pid&#39;=>3,&#39;name&#39;=>&#39;A@4&#39;];
$list[5]=[&#39;id&#39;=>5,&#39;pid&#39;=>0,&#39;name&#39;=>&#39;A@5&#39;];
$list[6]=[&#39;id&#39;=>6,&#39;pid&#39;=>1,&#39;name&#39;=>&#39;A@6&#39;];

//先初始化目录
$return=[];
foreach($list as $v)
    $return[$v[&#39;name&#39;]]=[];


//将每个目录与父目录进行拼接,并找到根目录
foreach($list as $k=>$v)
{
    if($v[&#39;pid&#39;]>=0)
        $return[$list[$v[&#39;pid&#39;]][&#39;name&#39;]][$v[&#39;name&#39;]]=&$return[$v[&#39;name&#39;]];
    else
        $parent=$v[&#39;name&#39;];

}

//打印根目录
print_r($return[$parent]);

登入後複製

输出1

Array(
    [A@1] => Array
        (
            [A@6] => Array
                (
                )

        )

    [A@2] => Array
        (
            [A@3] => Array
                (
                    [A@4] => Array
                        (
                        )

                )

        )

    [A@5] => Array
        (
        )

)

登入後複製

代码2

/**
 * Created by PhpStorm.
 * User: Nikaidou-Shinku
 * Date: 16/9/14
 * Time: 17:12
 */

$list[] = ['id' => 0, 'pid' => -1, 'name' => 'A@0'];//-1用于后面的根目录判断
$list[] = ['id' => 1, 'pid' => 0, 'name' => 'A@1'];
$list[] = ['id' => 2, 'pid' => 0, 'name' => 'A@2'];
$list[] = ['id' => 3, 'pid' => 2, 'name' => 'A@3'];
$list[] = ['id' => 4, 'pid' => 3, 'name' => 'A@4'];
$list[] = ['id' => 5, 'pid' => 0, 'name' => 'A@5'];
$list[] = ['id' => 6, 'pid' => 1, 'name' => 'A@6'];
//先初始化目录

$return = [];
$parent = '';

foreach ($list as $v)
    $return[$v['id']] = [
        'id' => $v['id'],
        'name' => $v['name'],
        'pid' => $v['pid'],
        'child' => '',
    ];


//将每个目录与父目录进行拼接,并找到根目录
foreach ($return as $k => $v) {
    if ($v['pid'] >= 0)

        $return[$v[&#39;pid&#39;]][&#39;child&#39;][$v[&#39;id&#39;]] = &$return[$k];

    else
        $parent = &$return[$k];
}
//打印根目录
var_export($parent);

登入後複製

输出2

$aa=[
        &#39;id&#39; => 0,
        &#39;name&#39; => &#39;A@0&#39;,
        &#39;pid&#39; => -1,
        &#39;child&#39; =>
            [
                1 =>
                    [
                        &#39;id&#39; => 1,
                        &#39;name&#39; => &#39;A@1&#39;,
                        &#39;pid&#39; => 0,
                        &#39;child&#39; =>
                            [
                                6 =>
                                    [
                                        &#39;id&#39; => 6,
                                        &#39;name&#39; => &#39;A@6&#39;,
                                        &#39;pid&#39; => 1,
                                        &#39;child&#39; => &#39;&#39;,
                                    ],
                            ],
                    ],
                2 =>
                    [
                        &#39;id&#39; => 2,
                        &#39;name&#39; => &#39;A@2&#39;,
                        &#39;pid&#39; => 0,
                        &#39;child&#39; =>
                            [
                                3 =>
                                    [
                                        &#39;id&#39; => 3,
                                        &#39;name&#39; => &#39;A@3&#39;,
                                        &#39;pid&#39; => 2,
                                        &#39;child&#39; =>
                                            [
                                                4 =>
                                                    [
                                                        &#39;id&#39; => 4,
                                                        &#39;name&#39; => &#39;A@4&#39;,
                                                        &#39;pid&#39; => 3,
                                                        &#39;child&#39; => &#39;&#39;,
                                                    ],
                                            ],
                                    ],
                            ],
                    ],
                5 =>
                    [
                        &#39;id&#39; => 5,
                        &#39;name&#39; => &#39;A@5&#39;,
                        &#39;pid&#39; => 0,
                        &#39;child&#39; => &#39;&#39;,
                    ],
            ],
    ]

登入後複製

第三种：

接下来这个无限级分类更为的简单。可以简化成使用5行代码就可以完成。

function generateTree($items){
   $tree = array();
   foreach($items as $item){
       if(isset($items[$item[&#39;pid&#39;]])){
           $items[$item[&#39;pid&#39;]][&#39;son&#39;][] = &$items[$item[&#39;id&#39;]];
       }else{
           $tree[] = &$items[$item[&#39;id&#39;]];
       }
   }
   return $tree;
}
$items = array(
   1 => array(&#39;id&#39; => 1, &#39;pid&#39; => 0, &#39;name&#39; => &#39;安徽省&#39;),
   2 => array(&#39;id&#39; => 2, &#39;pid&#39; => 0, &#39;name&#39; => &#39;浙江省&#39;),
   3 => array(&#39;id&#39; => 3, &#39;pid&#39; => 1, &#39;name&#39; => &#39;合肥市&#39;),
   4 => array(&#39;id&#39; => 4, &#39;pid&#39; => 3, &#39;name&#39; => &#39;长丰县&#39;),
   5 => array(&#39;id&#39; => 5, &#39;pid&#39; => 1, &#39;name&#39; => &#39;安庆市&#39;),
);
print_r(generateTree($items));

登入後複製

可以看到下面打印的结果：

Array
(
    [0] => Array
        (
            [id] => 1
            [pid] => 0
            [name] => 安徽省
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [pid] => 1
                            [name] => 合肥市
                            [son] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 4
                                            [pid] => 3
                                            [name] => 长丰县
                                        )
 
                                )
 
                        )
 
                    [1] => Array
                        (
                            [id] => 5
                            [pid] => 1
                            [name] => 安庆市
                        )
 
                )
 
        )
 
    [1] => Array
        (
            [id] => 2
            [pid] => 0
            [name] => 浙江省
        )
 
)

登入後複製

上面生成树方法还可以精简到5行：

function generateTree($items){
    foreach($items as $item)
        $items[$item[&#39;pid&#39;]][&#39;son&#39;][$item[&#39;id&#39;]] = &$items[$item[&#39;id&#39;]];
    return isset($items[0][&#39;son&#39;]) ? $items[0][&#39;son&#39;] : array();
}

登入後複製

但是上面的代码有个问题就是对数据库结构有点要求，每个节点要指明其父节点是谁，虽然实用性不高，但是还是能给大家带来启发，学习下不同类型的无限级分类。

本網站聲明

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn