php实现无限级分类查询(递归、非递归)

时间:2022-10-24 17:09:41

递归函数实现方式

上面提到,递归函数的也是借助于栈的机制实现的,但是底层对于栈的处理对于程序员来说都是透明的,程序员只需要关心应用的实现逻辑。所以说使用递归处理上述问题理解起来比较容易,代码也比较简洁。

既然使用递归函数,看名字我们就知道必须借助于自定义的函数。我先大概说一下其实现思路,具体细节我们反映在代码中。

对于每一层的函数其主要做的工作就是查找父Id为当前Id的栏目,查找到以后再次调用自身函数,将查找到的栏目的id作为下一层的父id。

其流程图如下

php实现无限级分类查询(递归、非递归)

不知道对于上面的解释大家能不能理解,没关系我们下面直接看代码

 1 <?php
2 /**
3 * 个人博客:迹忆博客
4 * 博客地址:www.onmpw.com
5 * 递归实现无限极分类
6 */
7 $channels = array(
8 array('id'=>1,'name'=>"衣服",'parId'=>0),
9 array('id'=>2,'name'=>"书籍",'parId'=>0),
10 array('id'=>3,'name'=>"T恤",'parId'=>1),
11 array('id'=>4,'name'=>"裤子",'parId'=>1),
12 array('id'=>5,'name'=>"鞋子",'parId'=>1),
13 array('id'=>6,'name'=>"皮鞋",'parId'=>5),
14 array('id'=>7,'name'=>"运动鞋",'parId'=>5),
15 array('id'=>8,'name'=>"耐克",'parId'=>7),
16 array('id'=>9,'name'=>"耐克",'parId'=>3),
17 array('id'=>10,'name'=>"鸿星尔克",'parId'=>7),
18 array('id'=>11,'name'=>"小说",'parId'=>2),
19 array('id'=>12,'name'=>"科幻小说",'parId'=>11),
20 array('id'=>13,'name'=>"古典名著",'parId'=>11),
21 array('id'=>14,'name'=>"文学",'parId'=>2),
22 array('id'=>15,'name'=>"四书五经",'parId'=>14)
23 );
24 $html = array();
25 /**
26 * 递归查找父id为$parid的结点
27 * @param array $html 按照父-》子的结构存放查找出来的结点
28 * @param int $parid 指定的父id
29 * @param array $channels 数据数组
30 * @param int $dep 遍历的深度,初始化为1
31 */
32 function getChild(&$html,$parid,$channels,$dep){
33 /*
34 * 遍历数据,查找parId为参数$parid指定的id
35 */
36 for($i = 0;$i<count($channels);$i++){
37 if($channels[$i]['parId'] == $parid){
38 $html[] = array('id'=>$channels[$i]['id'],'name'=>$channels[$i]['name'],'dep'=>$dep);
39 getChild($html,$channels[$i]['id'],$channels,$dep+1);
40 }
41 }
42 }
43 getChild($html,0,$channels,1);
44 ?>

这是递归实现无限级栏目查询的核心代码,结合图一对其实现流程应该有一个较清晰的认识。

非递归,即使用栈机制实现无限级栏目的查询

在上面我们大概介绍了一下使用递归的方式实现无限级栏目的查询,下面我们简单介绍一下非递归的方式。虽说不用递归函数的方式,但是鉴于无限级栏目的结构页需要参考递归的实现机制——栈的机制,解决这一问题。

在上学的时候老师就说,其实栈的核心机制也就四个字:先进后出。

在这对于栈的机制不多说,主要说一下如何借助栈实现无限级栏目查询。

1. 首先将*栏目压入栈中

2. 将栈顶元素出栈

3. 将出栈元素存入数组中,标记其深度(其深度就是在其父栏目的深度上面加1)

4. 以出栈的元素为父栏目,查找其子栏目

5. 将查找到的子栏目入栈,重复步骤2

6. 判断栈为空的话,流程结束;

通过对以上步骤的翻译,可以将这些步骤翻译成PHP代码,其核心代码如下

 1 <?php
2 /**
3 * 个人博客:迹忆博客
4 * 博客地址:www.onmpw.com
5 *使用非递归,即使用栈的方式实现栏目的无限极分类查询
6 */
7 $channels = array(
8 array('id'=>1,'name'=>"衣服",'parId'=>0),
9 array('id'=>2,'name'=>"书籍",'parId'=>0),
10 array('id'=>3,'name'=>"T恤",'parId'=>1),
11 array('id'=>4,'name'=>"裤子",'parId'=>1),
12 array('id'=>5,'name'=>"鞋子",'parId'=>1),
13 array('id'=>6,'name'=>"皮鞋",'parId'=>5),
14 array('id'=>7,'name'=>"运动鞋",'parId'=>5),
15 array('id'=>8,'name'=>"耐克",'parId'=>7),
16 array('id'=>9,'name'=>"耐克",'parId'=>3),
17 array('id'=>10,'name'=>"鸿星尔克",'parId'=>7),
18 array('id'=>11,'name'=>"小说",'parId'=>2),
19 array('id'=>12,'name'=>"科幻小说",'parId'=>11),
20 array('id'=>13,'name'=>"古典名著",'parId'=>11),
21 array('id'=>14,'name'=>"文学",'parId'=>2),
22 array('id'=>15,'name'=>"四书五经",'parId'=>14)
23 );
24 $stack = array(); //定义一个空栈
25 $html = array(); //用来保存各个栏目之间的关系以及该栏目的深度
26 /*
27 * 自定义入栈函数
28 */
29 function pushStack(&$stack,$channel,$dep){
30 array_push($stack, array('channel'=>$channel,'dep'=>$dep));
31 }
32 /*
33 * 自定义出栈函数
34 */
35 function popStack(&$stack){
36 return array_pop($stack);
37 }
38 /*
39 * 首先将*栏目压入栈中
40 */
41 foreach($channels as $key=>$val){
42 if($val['parId'] == 0)
43 pushStack($stack,$val,0);
44 }
45 /*
46 * 将栈中的元素出栈,查找其子栏目
47 */
48 do{
49 $par = popStack($stack); //将栈顶元素出栈
50 /*
51 * 查找以此栏目为父级栏目的id,将这些栏目入栈
52 */
53 for($i=0;$i<count($channels);$i++){
54 if($channels[$i]['parId'] == $par['channel']['id']){
55 pushStack($stack,$channels[$i],$par['dep']+1);
56 }
57 }
58 /*
59 * 将出栈的栏目以及该栏目的深度保存到数组中
60 */
61 $html[] = array('id'=>$par['channel']['id'],'name'=>$par['channel']['name'],'dep'=>$par['dep']);
62 }while(count($stack)>0);

上面就是使用非递归方式实现的。