无限级分类在开发中经常使用，例如：部门结构、文章分类。无限级分类的难点在于“输出”和“查询”，例如
- 将文章分类输出为<ul>列表形式；
- 查找分类A下面所有分类包含的文章。
1.实现原理
几种常见的实现方法，各有利弊。其中“改进前序遍历树”数据结构，便于输出和查询，但是在移动分类和常规理解上有些复杂。
2.数据结构
|
1
2
3
4
5
6
7
8
9
10
11
12
|
<?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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
<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构造可折叠树）十分方便。具体实现程序如下：
|
1
|
<ul><?php echo get_tree_ul($list, 1); ?></ul> |
4.输出option列表形式
|
1
2
3
4
5
6
7
8
9
|
<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> |
具体实现程序如下：
|
1
2
3
4
5
6
7
8
9
|
<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. 查找某一分类的所有子类
|
1
2
3
4
|
<?php $children = get_tree_child($list, 0); echo implode(',', $children); // 输出：1,3,2,7,6,5,8,4?> |
6. 查找某一分类的所有父类
|
1
2
3
4
|
<?php $children = get_tree_parent($list, 4); echo implode(',', $children); //8, 2, 10?> |
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
<?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实现无限极分类，希望对大家的学习有所帮助。
