Jeffrey Wang
文章70
标签131
分类16
一道关于无限级分类的测试题

一道关于无限级分类的测试题

题目内容

写一个函数,通过递归调用将以下数组打印出来:

$arr = array( array(‘id’=>1, ‘pid‘=>0, ‘text’=>‘1’), array(‘id’=>2, ‘pid‘=>0, ‘text’=> ‘2’), array(‘id’=>3, ‘pid‘=>0, ‘text’=> ‘3’), array(‘id’=>4, ‘pid‘=>0, ‘text’=> ‘4’), array(‘id’=>5, ‘pid‘=>0, ‘text’=> ‘5’), array(‘id’=>6, ‘pid‘=>0, ‘text’=> ‘6’), array(‘id’=>7, ‘pid‘=>3, ‘text’=> ‘3.1’), array(‘id’=>8, ‘pid‘=>3, ‘text’=> ‘3.2’), array(‘id’=>9, ‘pid‘=>3, ‘text’=> ‘3.3’), array(‘id’=>10, ‘pid‘=>9, ‘text’=> ‘3.3.1’), array(‘id’=>11, ‘pid‘=>9, ‘text’=> ‘3.3.1’), array(‘id’=>12, ‘pid‘=>9, ‘text’=> ‘3.3.1’), ); 要求打印的结果: 1 2 3 ——–3.1 ——–3.2 ——–3.3 —————-3.3.1 —————-3.3.2 —————-3.3.3 4 5 6

题目分析

使用pid指向父级元素id是 “无限级分类”的常用表示方法,观察题目的输出可知,这是一个深度遍历,从顶级节点开始遍历,如果某个节点下有子节点,则优先遍历子节点,直到顶级节点遍历完毕。

代码实现

下面贴出博主编写的代码:

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
<?php

/**
* @Author: JeffreyWang
* @Date: 2018-08-08 16:24:25
* @Last Modified by: 94468
* @Last Modified time: 2018-08-08 16:37:14
*/
namespace Wang\Lib;
class InfiniteTree{
protected $treedata = null;
/**
* 构造函数
* @param [type] $arr [树的数组数据,必须包含id和pid]
*/
function __construct($arr){
$this->init($arr);
}
/**
* 初始化函数
* @param [type] $arr [树的数组数据,必须包含id和pid]
* @return [type] [description]
*/
function init($arr){
$this->treedata = $arr;
}
/**
* 按照规则遍历树
* @param integer $pid [description]
* @param integer $dept [description]
* @param string $split [description]
* @return [type] [description]
*/
public function tranverse($pid = 0, $dept = 0, $split="--------"){
$data = array();
// 查找符合要求的数据
foreach($this->treedata as $key => $value){
if($value['pid'] == $pid){
if($dept){
// 只有dept>0才重复字符串
echo str_repeat($split, $dept);
}
echo $value['text']."<br/>\n";
// 调用下一层
$this->tranverse($value['id'], $dept+1, $split);
}
}
}
}
$arr = array(
array('id'=>1, 'pid'=>0, 'text'=>'1'),
array('id'=>2, 'pid'=>0, 'text'=> '2'),
array('id'=>3, 'pid'=>0, 'text'=> '3'),
array('id'=>4, 'pid'=>0, 'text'=> '4'),
array('id'=>5, 'pid'=>0, 'text'=> '5'),
array('id'=>6, 'pid'=>0, 'text'=> '6'),
array('id'=>7, 'pid'=>3, 'text'=> '3.1'),
array('id'=>8, 'pid'=>3, 'text'=> '3.2'),
array('id'=>9, 'pid'=>3, 'text'=> '3.3'),
array('id'=>10, 'pid'=>9, 'text'=> '3.3.1'),
array('id'=>11, 'pid'=>9, 'text'=> '3.3.1'),
array('id'=>12, 'pid'=>9, 'text'=> '3.3.1'),
);
$obj = new InfiniteTree($arr);
$obj->tranverse();
输出结果

总结

仔细观察输出结果,确定是深度遍历/广度遍历即可解决问题

本文作者:Jeffrey Wang
本文链接:https://blog.wj2015.com/2018/08/08/%E4%B8%80%E9%81%93%E5%85%B3%E4%BA%8E%E6%97%A0%E9%99%90%E7%BA%A7%E5%88%86%E7%B1%BB%E7%9A%84%E6%B5%8B%E8%AF%95%E9%A2%98/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×