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

2018年08月08日

题目内容

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

$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是 “无限级分类”的常用表示方法，观察题目的输出可知，这是一个深度遍历，从顶级节点开始遍历，如果某个节点下有子节点，则优先遍历子节点，直到顶级节点遍历完毕。

代码实现

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

<?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();

输出结果

总结

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