一、邻接表模型
邻接表模型中，数据表中的每项包含了指向其父项的指示器，最上层项的父项为0
建立表结构：
CREATE TABLE `category`(
`id` int not null auto_increment primary key comment '类目ID',
`name` varchar(30) not null comment '类目名',
`pid` int not null default 0 comment '父ID'
)ENGINE=MyISAM AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT='分类表';
特点
- 通过这种数据库设计出的无限级，读取的时候相当麻烦。
- 所以大部分的程序最多3到4级分类，这就足以满足需求，从而一次性读出所有的数据，再对得到数组或者对象进行递归。
- 本身负荷还是没太大问题。但是如果分类到更多级，那是不可取的办法。这样看来这种方法就是增删改的时候轻松了。然而就二级分类而言，采用这种算法就应该算最优先了。
PHP处理
递归方式
/**
* 数据集组合分类树(一维数组)
* @param cate 分类查询结果集
* @param html 格式串
* @return array
*/
function list_to_tree($cate,$html = '--',$pid = 0,$level = 0){
$arr = array();
foreach($cate as $v){
if($pid == $v['pid']){
$v['level'] = $level + 1;
$v['html'] = str_repeat($html,$level);
$arr[] = $v;
$arr = array_merge($arr,list_to_tree($cate,$html,$v['id'],$level+1));
}
}
return $arr;
}
/**
* 数据集组合分类树(多维数组)
* @param cate 分类结果集
* @param child 子树
* @return array
*/
function list_to_tree2($cate,$child = 'child',$pid = 0){
$arr = array();
foreach($cate as $v){
if($v['pid'] == $pid){
$v[$child] = list_to_tree2($cate,$child,$v['id']);
$arr[] = $v;
}
}
return $arr;
}
/**
* 通过子级ID返回父级
* @param cate 分类结果集
*/
function get_parents_by_id($cate,$id){
$arr = array();
foreach($cate as $v){
if($v['id'] == $id){
$arr[] = $v;
$arr = array_merge(get_parents_by_id($cate,$v['pid']),$arr);
}
}
return $arr;
}
/**
* 通过父级ID返回子级
* @param cate 分类结果集
*/
function get_childs_by_pid($cate,$pid){
$arr = array();
foreach($cate as $v){
if($v['pid'] == $pid){
$arr[] = $v;
$arr = array_merge($arr,get_childs_by_pid($cate,$v['id']));
}
}
return $arr;
}
非递归方式
//栈
function list_2_tree($list, $pid = 0)
{
$tree = [];
if(!is_array($list) || empty($list)){
return false;
}
//先将数组反转，因为出栈时会优先出最上面的
$list = array_reverse($list);
//先取出顶级的分类元素压入数组$stack中，并删除在$list中的
$stack = [];
foreach ($list as $key => $value) {
if ($value['pid'] == $pid) {
array_push($stack,$value);
unset($list[$key]);
}
}
while (count($stack)) {
//先从栈中取出第一项
$info = array_pop($stack);
//查找子节点
foreach ($list as $key => $child) {
//如果有子节点则入栈，用以后续继续查找子节点的下级
if ($child['pid'] == $info['id']) {
array_push($stack, $child);
unset($list[$key]);
}
}
//组装成下拉菜单格式
$tree[$info['id']] = $info['name'];
}
return $tree;
}
//引用
function getTree($list, $pid = 0)
{
$tree = [];
if (!empty($list)) {
//先修改为以id为下标的列表
$newList = [];
foreach ($list as $k => $v) {
$newList[$v['id']] = $v;
}
//然后开始组装成特殊格式
foreach ($newList as $value) {
if ($pid == $value['pid']) {
//先取出顶级
$tree[] = &$newList[$value['id']];
} elseif (isset($newList[$value['pid']])) {
//再判定非顶级的pid是否存在，如果存在，则再pid所在的数组下面加入一个字段items，来将本身存进去
$newList[$value['pid']]['items'][] = &$newList[$value['id']];
}
}
}
return $tree;
}
function formatTree($tree)
{
$options = [];
if (!empty($tree)) {
foreach ($tree as $key => $value) {
$options[$value['id']] = $value['name'];
if (isset($value['items'])) {
//查询是否有子节点
$optionsTmp = formatTree($value['items']);
if (!empty($optionsTmp)) {
$options = array_merge($options, $optionsTmp);
}
}
}
}
return $options;
}
//先调用getTree，再调用formatTree，formatTree虽然是递归，但是通过了getTree的特殊处理，效率有很大提高。
注意
在删除节点的时候要特别小心，因为潜在的可能会孤立一棵子树
二、预排序遍历树
timg.jpg
为树状的结构编号时，从左到右，一次一层，为节点赋右值前先从左到右遍历其子节点给其子节点赋左右值。这种方法被称作改进的先序遍历算法或者左右值。
- 每一个 后代节点 的 左值 > 父节点 的 左值
- 每一个 后代节点 的 右值 < 父节点的 右值
- 每一个节点的 右值 > 左值
改进的先序遍历算法便于输出和查询，但是在移动分类和常规理解上有些复杂。
建立表结构：
CREATE TABLE `category`(
`id` int not null auto_increment primary key comment '分类ID',
`name` varchar(30) not null comment '类目名',
`lft` int not null comment '左值',
`rgt` int not null comment '右值'
)ENGINE=MyISAM AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT='分类表';
查询
检索所有叶子节点(叶子节点的左右值是连续的，要检索出叶子节点，我们只要查找满足 rgt = lft+1 的节点。)
SELECT id,name FROM category WHERE rgt = lft + 1;
检索单一路径(以node节点为例)
SELECT id,name FROM category WHERE lft BETWEEN node.lft AND node.rgt;
检索节点深度(以node节点为例)
SELECT (COUNT(1) - 1) as level FROM category WHERE lft BETWEEN node.lft AND node.rgt;
检索整个树深度
SELECT node.id, CONCAT( REPEAT('----', COUNT(parent.label) - 1), node.label) AS label
FROM category AS node,category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.id
ORDER BY node.lft;
****结果****
一级分类
----二级分类
--------三级分类
--------三级分类
一级分类
----二级分类
--------三级分类
查询所有子节点(以node节点为例)
SELECT id,name FROM category WHERE lft > node.lft AND rgt < node.rgt;
新增节点
-
新增顶级分类：
- 获取该树中 最大右值
- 左值 = 最大右值 + 1
- 右值 = 最大右值 + 2
-
新增子节点：
- 首先获取父节点右值
UPDATE `catagory` SET `lft` = `lft`+2 WHERE `lft`> `父节点右值`
UPDATE `catagory` SET `rgt` = `rgt` + 2 WHERE `rgt`>= `父节点右值`
- 插入新节点：新增节点左值 = 父节点右值 新增节点右值 = 新增节点左值 + 1
删除节点
- 获取删除节点的左右值 node.lft, node.rgt
- 删除该节点以及所有后代节点
DELETE FROM `catagory` WHERE `lft`>= node.lft AND `rgt`<= node.rgt;
- 更新左右值
$Value= node.rgt - node.lft + 1;
UPDATE `catagory` SET `lft`=`lft`- $Value WHERE `lft`> node.lft;
UPDATE `catagory` SET `rgt`=`rgt`- $Value WHERE `rgt`> node.rgt;
数据集组合分类树（多维数组）
function get_all_tree(){
$sql = "select `id`,`name`, `lft`, `rgt`, 1 as `level` from `category` where uniacid = '{$uniacid}' order by `lft` asc";
$data = pdo_fetchall($sql);
if (!$data) {
return false;
}
$P[1] = -1;//记录某层节点对应的父节点
$prenode = '';//上一个节点
foreach ($data as $key => &$v) {
if ($key == 0) {
$data[$P[$v['level']]]['children'][] = &$v;
continue;
}
$prenode = $data[$key - 1];
# 如果连续的两个节点 c 和 p 的左值增加幅度为 1，则说明其深度增加了 1
# 且 p 为 c 及 c 的兄弟节点的父节点
if ($v['lft'] == $prenode['lft'] + 1) {
$v['level'] = $prenode['level'] + 1;
if ($prenode['level'] > count($P)) {
$P[count($P) + 1] = $key - 1;
}else{
$P[$v['level']] = $key - 1;
}
}elseif ($v['lft'] > $data[$P[$prenode['level']]]['rgt']) {
# 如果 c 的左值大于 p 的父节点的右值，则说明 p 与 c 并非兄弟节点
# 并可以计算出两节点的深度差为 c 的左值与 p 的右值之差减 1
$v['level'] = $prenode['level'] - ($v['lft'] - $prenode['rgt'] - 1);
}else{
# 不满足以上两个条件，说明 c 是 p 的兄弟节点
$v['level'] = $prenode['level'];
}
$data[$P[$v['level']]]['children'][] = &$v;
}
return $data[-1]['children'];
}
