一、参考资料
http://www.php.cn/php-weizijiaocheng-360446.html
http://www.php.cn/keywords-无限极分类.html
本文博客部分内容是上述网上内容搬运过来的。
二、场景
无限极分类在web网站中应用很多，比如无限极菜单，无限极文件夹展开。因为最近的项目中有用到树的结构，其实就是无限极菜单的存储。
在某次面试中也有提及，所以这里集合上述网上的资料总结一下。
使用场景：
1、需要获取所有的节点，也就是无限极菜单的树形结构分类。
2、获取某个节点的所有叶子节点。
3、获取某个节点的所有子孙节点。
4、非叶子节点的分页展示。
三、数据库存储
无限极分类其实就是一棵树，所有的节点作为一个存储元素。每个节点可以有任意个孩子节点，且只有一个父节点。
MySQL数据存储，结合项目的数据表存储结构如下：
CREATE TABLE t_tree_info (
`Fid` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '标签自增ID',
`Fname` varchar(255) NOT NULL DEFAULT '' COMMENT '节点名称',
`Fpid` bigint(20) unsigned NOT NULL DEFAULT 0 COMMENT '父节点id',
`Fadd_time` TIMESTAMP NOT NULL DEFAULT '0000-00-00 00:00:00' COMMENT '创建时间',
`Fmodify_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
PRIMARY KEY (`Fid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='无限极分类菜单存储表';
核心字段就是节点自身唯一标识Fid，和对应的父节点标识Fpid。
四、技术实现
全局数据存储节点
节点数据在项目中是MySQL存储的，现在为了测试，把MySQL数据直接存放到数组里面，全局使用。数据存储如下：
private static $listData = [
[
"Fid" => 1,
"Fpid" => 8,
"Fname" => '首页',
],
[
"Fid" => 2,
"Fpid" => 8,
"Fname" => '博客',
],
[
"Fid" => 3,
"Fpid" => 8,
"Fname" => '官网',
],
[
"Fid" => 4,
"Fpid" => 2,
"Fname" => '个人博客',
],
[
"Fid" => 5,
"Fpid" => 2,
"Fname" => '他人博客',
],
[
"Fid" => 6,
"Fpid" => 8,
"Fname" => '测试1',
],
[
"Fid" => 7,
"Fpid" => 8,
"Fname" => '测试2',
],
[
"Fid" => 8,
"Fpid" => 0,
"Fname" => '无限极分类',
],
[
"Fid" => 9,
"Fpid" => 5,
"Fname" => '女性栏目',
],
[
"Fid" => 10,
"Fpid" => 5,
"Fname" => '男性栏目',
],
];
引用方式实现无限极分类
思路：
1、即所有待处理的数据进行包装成下标为主键Fid（pk）的数组，便于由Fpid获取对应的父栏目。
2、对包装的数据进行循环，如果为根节点，则将其引用添加到tree中，否则，将其引用添加到其父类的子元素中。这样虽然tree中，只是添加了根节点，但是每个根节点如果有子元素，其中包含了子元素的引用。故能形成树型。
个人觉得引用的设计思路相比递归的思路更容易理解，更直观一些。
代码如下：
/**
* 把返回的数据集转换成Tree
* @param array $list 要转换的数据集
* @param string $pk 自增字段（栏目Fid）
* @param string $pid parent标记字段
* @return array
*/
public static function quote_make_tree($list, $pk = 'Fid', $pid = 'Fpid',$child = '_child', $root = 0)
{
$tree = $packData = [];
foreach ($list as $data) {
$packData[$data[$pk]] = $data;
}
foreach ($packData as $key =>$val) {
if ($val[$pid] == $root) {//代表跟节点
$tree[] = & $packData[$key];
} else {
//找到其父类
$packData[$val[$pid]][$child][] = & $packData[$key];
}
}
return $tree;
}
引用调用树：
/**
* 引用生成树
* @return
*/
public static function quote_tree_test()
{
$tree = self::make_tree(self::$listData, $pk = 'id', $pid = 'pid', $child = '_child', $root = 0);
echo json_encode($tree);
}
返回结果如下：
[
{
"Fid": 8,
"Fpid": 0,
"Fname": "无限极分类",
"_child": [
{
"Fid": 1,
"Fpid": 8,
"Fname": "首页"
},
{
"Fid": 2,
"Fpid": 8,
"Fname": "博客",
"_child": [
{
"Fid": 4,
"Fpid": 2,
"Fname": "个人博客"
},
{
"Fid": 5,
"Fpid": 2,
"Fname": "他人博客",
"_child": [
{
"Fid": 9,
"Fpid": 5,
"Fname": "女性栏目"
},
{
"Fid": 10,
"Fpid": 5,
"Fname": "男性栏目"
}
]
}
]
},
{
"Fid": 3,
"Fpid": 8,
"Fname": "官网"
},
{
"Fid": 6,
"Fpid": 8,
"Fname": "测试1"
},
{
"Fid": 7,
"Fpid": 8,
"Fname": "测试2"
}
]
}
]
递归方式实现无限分类
思路：
1、使用循环，分别获取所有的根节点。
2、在获取每个节点的时候，将该节点从原数据中移除，并递归方式获取其所有的子节点，一直原数据为空。
代码如下：
/**
* 递归生成树
* @param array $list 要转换的数据集
* @param string $pk 自增字段（栏目id）
* @param string $pid parent标记字段
* @param string $child 孩子节点key
* @param integer $root 根节点标识
* @return array
*/
public static function recursive_make_tree($list, $pk = 'Fid', $pid = 'Fpid', $child = '_child', $root = 0)
{
$tree = [];
foreach ($list as $key => $val) {
if ($val[$pid] == $root) {
//获取当前$pid所有子类
unset($list[$key]);
if (!empty($list)) {
$child = self::recursive_make_tree($list, $pk, $pid, $child, $val[$pk]);
if (!empty($child)) {
$val['_child'] = $child;
}
}
$tree[] = $val;
}
}
return $tree;
}
递归调用树：
public static function recursive_tree_test()
{
$tree = self::recursive_make_tree(self::$listData, $pk = 'Fid', $pid = 'Fpid', $child = '_child', $root = 0);
echo json_encode($tree);
}
获取某个节点的所有叶子节点
思路：
1、如果当前节点不是某个节点的父节点，则说明当前节点是叶子节点。则返回当前节点。同时也是递归出口。
2、如果当前节点是某个节点的父节点，则说明当前节点不是叶子节点。针对当前节点的孩子节点进行同样递归查询。
代码如下：
/**
* 获取某节点的所有叶子节点
* 如果当前节点是叶子节点，则返回本身
* @param $pid
* @return array
*/
public static function getAllLeafNodeByFatherIds($pid )
{
$allLeafTagIds = [];
$sql = "SELECT GROUP_CONCAT(Fid) AS Fid FROM t_tree_info WHERE Fpid={$pid}";
$res = $this->db->fetchRow($sql);
if ($res && $res['Fid']) {
$leafTagIds = explode(',', $res['Fid']);
foreach ($leafTagIds as $nodeTagId) {
$curLeafTagIds = $this->getAllLeafNodeByFatherIds($nodeTagId);
if ($curLeafTagIds) {
$allLeafTagIds = array_merge($allLeafTagIds, $curLeafTagIds);
}
}
return $allLeafTagIds;
} else {
// 当前节点是叶子节点，返回该节点
return [$tagId];
}
}
获取某个节点的所有子孙节点
思路：
1、如果当前节点不是某个节点的父节点，说明当前节点是叶子节点，则返回空。同时也是递归出口。
2、如果当前节点是某个节点的父节点，则合并当前节点到返回数组中；然后对该节点的所有孩子节点进行同样的递归查询。
代码如下：
/**
* 根据父节点获取所有的子节点
* @param $pids
* @return array
*/
public static function getAllChildNodeByFatherIds($pids)
{
if (!is_array($pids) || empty($pids)) {
return [];
}
$allChildTagIds = [];
$tagIdsStr = implode(',', array_unique($pids));
$sql = "SELECT GROUP_CONCAT(Fid) AS Fid FROM t_tree_info WHERE Fpid IN({$tagIdsStr})";
$res = $this->db->fetchRow($sql);
if ($res && $res['Fid']) {
$childTagIds = explode(',', $res['Fid']);
// 合并当前查询出的子节点
$allChildTagIds = array_merge($allChildTagIds, $childTagIds);
$curChildTagIds = $this->getAllChildNodeByFatherIds($childTagIds);
// 如果再查询出子节点
$allChildTagIds = array_merge($allChildTagIds, $curChildTagIds);
return $allChildTagIds;
} else {
return [];
}
}
非叶子节点的分页展示
思路：
1、获取非叶子节点，只要节点不是其他节点的父节点即可。
代码如下：
# MySQL分页查询语句
SELECT SQL_CALC_FOUND_ROWS Fid, Fname, Fpid, Fadd_time, Fmodify_time FROM t_tree_info WHERE Fid IN(SELECT DISTINCT Fpid FROM t_tree_info) ORDER BY Fadd_time DESC LIMIT 0, 10