1、递归 - 分层数据 Hierarchical Data 探索

1、递归 - 分层数据 Hierarchical Data 探索

引言

什么是分层数据?(例如:无限级分类、多级菜单、省份城市)

类似于树形结构,除了根节点和叶子节点外,所有节点都有一个父节点和一个或多个子节点。

大多数同学都曾在数据库中处理过分层数据(hierarchical data),分层数据存在于许多基于数据库的应用程序中,包括论坛和邮件列表中的分类、商业组织图表、内容管理系统的分类、产品分类、无限级分类、多级菜单、省份城市等等。但是因为关系数据库中的表没有层次关系,只是简单的平面化的列表;而分层数据具有父-子关系,显然关系数据库中的表不能自然地表现出其分层的特性。

接下来我会先通过一般方法和递归(recursion)方法来实现无限极分类,然后再通过两种数据模型来谈一谈分层数据的处理。

三种方式的变量传递

  • & 引用赋值
1
2
3
4
5
6
7
8
9
function doloop1(&$i = 1)
{
print_r($i);
$i++;
if ($i <= 10) {
doloop1($i);
}
}
doloop1();
  • static 静态变量
1
2
3
4
5
6
7
8
9
10
11
function doloop2()
{
static $i = 1;
print_r($i);
$i++;
if ($i <= 10) {
doloop2();
}
}

doloop2();
  • global 全局变量
1
2
3
4
5
6
7
8
9
10
11
$i = 1;
function doloop3()
{
global $i;
echo $i;
$i++;
if ($i <= 10) {
doloop3();
}
}
doloop3();

构建模拟数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 模拟数据
$data = [
['id' => 1, 'title' => 'Electronics', 'parent_id' => 0],
['id' => 2, 'title' => 'Laptops & PC', 'parent_id' => 1],
['id' => 3, 'title' => 'Laptops', 'parent_id' => 2],
['id' => 4, 'title' => 'PC', 'parent_id' => 2],
['id' => 5, 'title' => 'Cameras & photo', 'parent_id' => 1],
['id' => 6, 'title' => 'Camera', 'parent_id' => 5],
['id' => 7, 'title' => 'Phones & Accessories', 'parent_id' => 1],
['id' => 8, 'title' => 'Smartphones', 'parent_id' => 7],
['id' => 9, 'title' => 'Android', 'parent_id' => 8],
['id' => 10, 'title' => 'iOS', 'parent_id' => 8],
['id' => 11, 'title' => 'Other Smartphones', 'parent_id' => 8],
['id' => 12, 'title' => 'Batteries', 'parent_id' => 7],
['id' => 13, 'title' => 'Headsets', 'parent_id' => 7],
['id' => 14, 'title' => 'Screen Protectors', 'parent_id' => 7],
];

获取无限极分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* 值引用获取无限极分类树
*
* @param array $data
* @return array
*/
function make_tree($data)
{
$refer = array();
$tree = array();
foreach($data as $k => $v){
$refer[$v['id']] = & $data[$k]; //创建主键的数组引用
}

foreach($data as $k => $v){
$parent_id = $v['parent_id']; //获取当前分类的父级id
if($parent_id == 0){
$tree[] = & $data[$k]; //顶级栏目
}else{
if(isset($refer[$parent_id])){
$refer[$parent_id]['children'][] = & $data[$k]; //如果存在父级栏目,则添加进父级栏目的子栏目数组中
}
}
}

return $tree;
}

/**
* 递归获取无限极分类树
*
* @param array $data
* @param int $parent_id
* @param int $level
* @return array
*/
function make_tree2($data = [], $parent_id = 0, $level = 0)
{
$tree = [];
if ($data && is_array($data)) {
foreach ($data as $v) {
if ($v['parent_id'] == $parent_id) {
$tree[] = [
'id' => $v['id'],
'level' => $level,
'title' => $v['title'],
'parent_id' => $v['parent_id'],
'children' => make_tree2($data, $v['id'], $level + 1),
];
}
}
}
return $tree;
}

获取子节点以及节点的层级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* 引用赋值方式
* @param array $data
* @param int $id
* @param int $level
* @return array
*/
function getSubTree($data = [], $id = 0, $level = 0)
{
static $tree = [];

foreach ($data as $key => $value) {
if ($value['parent_id'] == $id) {
$value['laravel'] = $level;
$tree[] = $value;
getSubTree($data, $value['id'], $level + 1);
}
}
return $tree;
}

/**
* 静态变量方式
* @param array $data
* @param int $id
* @param int $level
* @return array
*/
function getSubTree($data = [], $id = 0, $level = 0)
{
static $tree = [];

foreach ($data as $key => $value) {
if ($value['parent_id'] == $id) {
$value['laravel'] = $level;
$tree[] = $value;
getSubTree($data, $value['id'], $level + 1);
}
}
return $tree;
}


/**
* 全局变量方式
* @param array $data
* @param int $id
* @param int $level
* @return array
*/

$tree = []; //先申明变量
function getSubTree($data = [], $id = 0, $level = 0)
{
global $tree;

foreach ($data as $key => $value) {
if ($value['parent_id'] == $id) {
$value['laravel'] = $level;
$tree[] = $value;
getSubTree($data, $value['id'], $level + 1);
}
}
return $tree;
}

通过pid获取所有上级分类 常用于面包屑导航

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* getParentsByParentId2($categories, 9)
*
* @param array $data
* @param $parent_id
* @return array
*/
function getParentsByParentId($data = [], $parent_id)
{
static $categories = [];

if ($data && is_array($data)) {
foreach ($data as $item) {
if ($item['id'] == $parent_id) {
$categories[] = $item;
getParentsByParentId($data, $item['parent_id']);
}
}
}
return $categories;
}

function getParentsByParentId2($data = [], $parent_id)
{
$categories = [];

if ($data && is_array($data)) {
foreach ($data as $item) {
if ($item['id'] == $parent_id) {
$categories[] = $item;
$categories = array_merge($categories, getParentsByParentId2($data, $item['parent_id']));
}
}
}
return $categories;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×