无限级分类在开发中经常使用，例如：部门结构、文章分类。无限级分类的难点在于“输出”和“查询”，例如
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. 相关函数
<?phpfunction 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实现无限极分类，希望对大家的学习有所帮助。
