search

Home >php教程 >PHP源码 >PHP实现无限级分类（不使用递归）

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

PHP中文网
PHP中文网Original
2016-05-25 17:13:081003browse

这篇文章主要介绍了在不使用递归的情况下PHP实现无限级分类，感兴趣的小伙伴们可以参考一下

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

  • 将文章分类输出为ff6d136ddc5fdfeffaf53ff6ee95f185列表形式；

  • 查找分类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;)
 );
?>

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

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

由于所有的递归均可以使用循环实现，本文根据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;
}
?>


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

Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：PHP实现逆波兰式 - 计算工资时用Next article：PHP和机场三字码的操作

Related articles

See more