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

前端技术 2023/09/02 PHP

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

  • 将文章分类输出为<ul>列表形式；
  • 查找分类A下面所有分类包含的文章。

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

2.数据结构

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

各分类之间通过父类id（即fid）进行级别“串联”，形成一棵分类树。在进行串联时候有一点值得注意：分类A的fid不可以是其子类的id。

在使用这种数据结构进行输出时最常用的算法就是“递归”，熟悉PHP语言的朋友肯定知道，PHP不擅长递归 ,而且递归次数有限（100次左右，因操作系统和配置而异）。

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

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

<ul>
 <li class=\"first-child\">
 <div>江苏</div>
 <ul>
 <li class=\"first-child last-child\">
 <div>无锡</div>
 <ul>
 <li class=\"first-child last-child\">
 <div>江阴</div>
 </li>
 </ul>
 </li>
 </ul>
 </li>
 <li class=\"last-child\">
 <div>安徽</div>
 <ul>
 <li class=\"first-child\"><div>芜湖</div></li>
 <li><div>合肥</div></li>
 <li class=\"last-child\"><div>蚌埠</div></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 \'<option value=\"\' . $op[\'id\'] .\'\">\' . str_repeat(\" \", $op[\'depth\'] * 4) . $op[\'title\'] . \'<;/option>\';
 }
?>
<;/select>

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

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

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

<?php
 $children = get_tree_parent($list, 4);
 echo implode(\',\', $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[\'fid\'] == $fid) {
 array_splice($data, $i , 1);
 $result[] = $node[\'id\'];
 $cids[] = $node[\'id\'];
 $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[\'id\']] = $node;
 } 

 $value = isset($obj[$id]) ? $obj[$id] : null; 
 while($value) {
 $id = null;
 foreach($data as $node) {
 if($node[\'id\'] == $value[\'fid\']) {
 $id = $node[\'id\'];
 $result[] = $node[\'id\'];
 break;
 }
 }
 if($id === null) {
 $result[] = $value[\'fid\'];
 }
 $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[\'fid\'];
 if(!isset($child[$pid])) {
 $child[$pid] = array();
 }
 array_push($child[$pid], $node[\'id\']);
 $obj[$node[\'id\']] = $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]][\'isLastChild\'] = true;
 $obj[$cids[0]][\'isFirstChild\'] = true;
 $flag = true;
 }
 if ($id != $fid && $node && !isset($added_left[$id])) {
 if(isset($node[\'isFirstChild\']) && isset($node[\'isLastChild\'])) {
 $html_left[] = \'<li class=\"first-child last-child\">\';
 } else if(isset($node[\'isFirstChild\'])) {
 $html_left[] = \'<li class=\"first-child\">\';
 } else if(isset($node[\'isLastChild\'])) {
 $html_left[] = \'<li class=\"last-child\">\';
 } else {
 $html_left[] = \'<li>\';
 } 
 $html_left[] = ($flag === true) ? \"<div>{$node[\'title\']}</div><ul>\" : \"<div>{$node[\'title\']}</div>\";
 $added_left[$id] = true;
 } 
 if ($id != $fid && $node && !isset($added_right[$id])) {
 $html_right[] = ($flag === true) ? \'</ul></li>\' : \'</li>\';
 $added_right[$id] = true;
 }

 if ($flag == false) {
 if($node) {
 $cids = $child[$node[\'fid\']];
 for ($i = count($cids) - 1; $i >= 0; $i--) {
 if ($cids[$i] == $id) {
 array_splice($child[$node[\'fid\']], $i, 1);
 break;
 }
 } 
 if(count($child[$node[\'fid\']]) == 0) {
 $child[$node[\'fid\']] = 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(\'\', $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[\'fid\'];
 if(!isset($child[$pid])) {
 $child[$pid] = array();
 }
 array_push($child[$pid], $node[\'id\']);
 $obj[$node[\'id\']] = $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[\'depth\'] = $depth;
 $options[] = $node;
 $added[$id] = true;
 }
 if($flag == true){
 $depth++;
 } else {
 if($node) {
 for ($i = count($child[$node[\'fid\']]) - 1; $i >= 0; $i--) {
 if ($child[$node[\'fid\']][$i] == $id) {
 array_splice($child[$node[\'fid\']], $i, 1);
 break;
 }
 } 
 if(count($child[$node[\'fid\']]) == 0) {
 $child[$node[\'fid\']] = null;
 $depth--;
 }
 }
 array_shift($stack);
 }
 $loop++;
 if($loop > 5000) return $options;
 }
 unset($child);
 unset($obj);
 return $options;
}
?>

以上介绍的就是在不使用递归的情况下php实现无限极分类，希望对大家的学习有所帮助。

本文地址：https://www.stayed.cn/item/3813

转载请注明出处。

本站部分内容来源于网络,如侵犯到您的权益,请 联系我

我的博客

人生若只如初见，何事秋风悲画扇。

我的标签

随笔档案