无限分类数据格式化成树
程序员文章站
2022-04-27 09:32:57
...
无限分类是web开发中经常遇到的，比如文章分类，商品分类，用户权限的分类等等。传统的做法是用递归的算法进行，而我们知道，递归即费时间，又费空间。那天下午，一哥们问无限分类，让我写个函数参考一下，当天晚上回去就开始，忙了四个多小时，终于写出来了，时间复杂度最小是n，最大是 2n-(一级分类的类别数量)，经过测试运效率的确比递归算法高
14, 'pid' => 1, 'name' => '二级14' ),则 $son_keys[9] = "[1]['son'][5]['son'][9]"，
* 则：$parent[1][14] = 14
*/
$parent = array(); //以键值作为父节点的子
/**
* 定义树中的所有子孙节点所对应的键值:
* 如 $tree[1]['son'][5]['son'][9]= array('id' => 9, 'pid' => 1, 'name' => '二级13' )
* 则 $son_keys[9] = "[1]['son'][5]['son'][9]"
*/
$son_keys = array();
foreach($items as $value){
//如果当前节点的父亲是一级（暂时是在一级）
if(isset($tree[$value['pid']])){
$tree[$value['pid']]['son'][$value['id']] = $value;
$son_keys[$value['id']] = "[{$value['pid']}]['son'][{$value['id']}]";
//如果有以当前节点作为父节点
if(isset($parent[$value['id']])){
foreach($parent[$value['id']] as $val){
$tree[$value['pid']]['son'][$value['id']]["son"][$val]=$tree[$val];
unset($tree[$val]);
$son_keys[$val] = "[{$value['pid']}]['son'][{$value['id']}]['son'][$val]";
}
unset($parent[$value['id']]);
}
}elseif(isset($son_keys[$value['pid']])){ //如果当前节点的父亲类是二级或以上
$current_key = "{$son_keys[$value['pid']]}['son'][{$value['id']}]";
$son_keys[$value['id']] = $current_key;
eval('$tree'.$current_key.'=$value;');
//如果有以当前节点作为父节点
if(isset($parent[$value['id']])){
foreach($parent[$value['id']] as $val){
eval('$tree'.$current_key.'["son"][$val]=$tree[$val];');
unset($tree[$val]);
$son_keys[$val] = "{$current_key}['son'][$val]";
}
unset($parent[$value['id']]);
}
}else{ //当前节点或暂时没有父亲
$tree[$value['id']] = $value;
//如果有以当前节点作为父节点
if(isset($parent[$value['id']])){
foreach($parent[$value['id']] as $val){
$tree[$value['id']]["son"][$val]=$tree[$val];
unset($tree[$val]);
$son_keys[$val] = "[{$value['id']}]['son'][$val]";
}
unset($parent[$value['id']]);
}
}
$parent[$value['pid']][$value['id']] = $value['id'];
}
return $tree;
}
/**
* 用于格式化数组，仅用于调试
* @author Xuefen.Tong
* @date 2012-06-17
*/
function div_print_r($ar)
{
echo '';
echo "";
print_r($ar);
echo "
";
echo "";
}
/**
* 以下这个类是从Ecamll中copy过来的
* 我这里用于和我的代码进行性能的对比
*
* 树 0是根结点
*/
class Tree
{
var $data = array();
var $child = array(-1 => array());//父亲节点与孩子节点的关系映射
var $layer = array(0 => 0);//初始节点为0
var $parent = array();//非叶子节点的节点，也就是有孩子节点的节点
var $value_field = '';//一般是分类名称
var $id_field = '';//子节点的名称
var $parent_field = '';//父节点的名称
/**
* 构造函数
*
* @param mix $value
*/
function __construct($value = 'root')
{
$this->setNode(0, -1, $value);
}
/**
* 构造树
*
* @param array $nodes 结点数组
* @param string $id_field
* @param string $parent_field
* @param string $value_field
*/
function setTree($nodes, $id_field, $parent_field, $value_field)
{
$this->value_field = $value_field;
$this->id_field =$id_field;
$this->parent_field = $parent_field;
foreach ($nodes as $node)
{
$this->setNode($node[$this->id_field], $node[$this->parent_field ], $node);
}
$this->setLayer();
}
/**
* 取得options
*
* @param int $layer
* @param int $root
* @param string $space
* @return array (id=>value)
*/
function getOptions($layer = 0, $root = 0, $except = NULL, $space = ' ')
{
$options = array();
$childs = $this->getChilds($root, $except);
foreach ($childs as $id)
{
if ($id > 0 && ($layer getLayer($id) getLayer($id, $space) . htmlspecialchars($this->getValue($id));
}
}
return $options;
}
/**
* 设置结点
*
* @param mix $id
* @param mix $parent
* @param mix $value
*/
function setNode($id, $parent, $value)
{
$parent = $parent ? $parent : 0;
$this->data[$id] = $value;
if (!isset($this->child[$id]))
{
$this->child[$id] = array();
}
if (isset($this->child[$parent]))
{
$this->child[$parent][] = $id;
}
else
{
$this->child[$parent] = array($id);
}
$this->parent[$id] = $parent;
}
/**
* 计算layer
*/
function setLayer($root = 0)
{
foreach ($this->child[$root] as $id)
{
$this->layer[$id] = $this->layer[$this->parent[$id]] + 1;
if ($this->child[$id]) $this->setLayer($id);
}
}
/**
* 先根遍历，不包括root
*
* @param array $tree
* @param mix $root
* @param mix $except 除外的结点，用于编辑结点时，上级不能选择自身及子结点
*/
function getList(&$tree, $root = 0, $except = NULL)
{
foreach ($this->child[$root] as $id)
{
if ($id == $except)
{
continue;
}
$tree[] = $id;
if ($this->child[$id]) $this->getList($tree, $id, $except);
}
}
function getValue($id)
{
return $this->data[$id][$this->value_field];
}
function getLayer($id, $space = false)
{
return $space ? str_repeat($space, $this->layer[$id]) : $this->layer[$id];
}
function getParent($id)
{
return $this->parent[$id];
}
/**
* 取得祖先，不包括自身
*
* @param mix $id
* @return array
*/
function getParents($id)
{
while ($this->parent[$id] != -1)
{
$id = $parent[$this->layer[$id]] = $this->parent[$id];
}
ksort($parent);
reset($parent);
return $parent;
}
function getChild($id)
{
return $this->child[$id];
}
/**
* 取得子孙，包括自身，先根遍历
*
* @param int $id
* @return array
*/
function getChilds($id = 0, $except = NULL)
{
$child = array($id);
$this->getList($child, $id, $except);
unset($child[0]);
return $child;
}
/**
* 先根遍历，数组格式 id,子id,value对应的值
* array(
* array('id' => '', 'value' => '', children => array(
* array('id' => '', 'value' => '', children => array()),
* ))
* )
*/
function getArrayList($root = 0 , $layer = NULL)
{
$data = array();
foreach ($this->child[$root] as $id)
{
if($layer && $this->layer[$this->parent[$id]] > $layer-1)
{
continue;
}
$data[] = array($this->id_field => $id,$this->value_field=> $this->getValue($id), 'children' => $this->child[$id] ? $this->getArrayList($id , $layer) : array());
// $data[] = array('id' => $id, 'value' => $this->getValue($id), 'children' => $this->child[$id] ? $this->getArrayList($id , $layer) : array());
}
return $data;
}
}
#-----------------------------------------------------------------------
#-------这组数据的特点是父类的数据在前面--------------------------------
#-------如果算法从父类开始，循环次数少，次数为18，正好时间复杂度正好是n-
#-------如果是其他数据，肯定小于这个数值--------------------------------
#-----------------------------------------------------------------------
$items1 = array(
array('id' => 1, 'pid' => 0, 'name' => '一级11' ),
array('id' => 11, 'pid' => 0, 'name' => '一级12' ),
array('id' => 2, 'pid' => 1, 'name' => '二级21' ),
array('id' => 10, 'pid' => 11, 'name' => '二级22' ),
array('id' => 3, 'pid' => 1, 'name' => '二级23' ),
array('id' => 12, 'pid' => 11, 'name' => '二级24' ),
array('id' => 9, 'pid' => 1, 'name' => '二级25' ),
array('id' => 14, 'pid' => 1, 'name' => '二级26' ),
array('id' => 4, 'pid' => 9, 'name' => '三级31' ),
array('id' => 6, 'pid' => 9, 'name' => '三级32' ),
array('id' => 7, 'pid' => 4, 'name' => '四级41' ),
array('id' => 8, 'pid' => 4, 'name' => '四级42' ),
array('id' => 5, 'pid' => 4, 'name' => '四级43' ),
array('id' => 13, 'pid' => 4, 'name' => '四级44' ),
array('id' => 15, 'pid' => 8, 'name' => '五级51' ),
array('id' => 16, 'pid' => 8, 'name' => '五级52' ),
array('id' => 17, 'pid' => 8, 'name' => '五级53' ),
array('id' => 18, 'pid' => 16, 'name' => '六级64' ),
);
#-----------------------------------------------------------------------
#-------这组数据的特点是父类的数据在后面--------------------------------
#-------在我写的函数里面，这级数据的循环次数最多，为34次，--------------
#-------如果是其他数据，肯定小于这个数值--------------------------------
#-----------------------------------------------------------------------
$items2 = array(
array('id' => 18, 'pid' => 16, 'name' => '六级64' ),
array('id' => 15, 'pid' => 8, 'name' => '五级51' ),
array('id' => 16, 'pid' => 8, 'name' => '五级52' ),
array('id' => 17, 'pid' => 8, 'name' => '五级53' ),
array('id' => 5, 'pid' => 4, 'name' => '四级43' ),
array('id' => 7, 'pid' => 4, 'name' => '四级41' ),
array('id' => 13, 'pid' => 4, 'name' => '四级44' ),
array('id' => 8, 'pid' => 4, 'name' => '四级42' ),
array('id' => 6, 'pid' => 9, 'name' => '三级32' ),
array('id' => 4, 'pid' => 9, 'name' => '三级31' ),
array('id' => 2, 'pid' => 1, 'name' => '二级21' ),
array('id' => 10, 'pid' => 11, 'name' => '二级22' ),
array('id' => 3, 'pid' => 1, 'name' => '二级23' ),
array('id' => 12, 'pid' => 11, 'name' => '二级24' ),
array('id' => 9, 'pid' => 1, 'name' => '二级25' ),
array('id' => 14, 'pid' => 1, 'name' => '二级26' ),
array('id' => 1, 'pid' => 0, 'name' => '一级11' ),
array('id' => 11, 'pid' => 0, 'name' => '一级12' ),
);
//两种不同顺序的数据的循环次数对比
$time1 = microtime(true);
$tree1 = genTree($items1);
$time2 = microtime(true);
$tree2 = genTree($items2);
$time3 = microtime(true);
//采用ecmall中tree类格式化数据算法
$tree = new Tree();
$tree->setTree($items1, 'id', 'pid', 'name');
$Ctree1 = $tree->getArrayList();
$time4 = microtime(true);
$tree = new Tree();
$tree->setTree($items2, 'id', 'pid', 'name');
$Ctree2 = $tree->getArrayList();
$time5 = microtime(true);
echo "function 时间1：",($time2-$time1),", 时间2：",($time3-$time2),"
";
echo "tree 类时间1：",($time4-$time3),", 时间2：",($time5-$time4),"
";
div_print_r($tree1);
div_print_r($tree2);
div_print_r($Ctree2);
div_print_r($Ctree1);
上一篇： 有关UTF-8 编码中BOM的检测与删除