无限分类数据格式化成树
2012-06-17 08:58:34 来源:WEB开发网核心提示: 无限分类是web开发中经常遇到的,比如文章分类,无限分类数据格式化成树,商品分类,用户权限的分类等等,这级数据的循环次数最多,为34次,传统的做法是用递归的算法进行,而我们知道
无限分类是web开发中经常遇到的,比如文章分类,商品分类,用户权限的分类等等。传统的做法是用递归的算法进行,而我们知道,递归即费时间,又费空间。那天下午,一哥们问无限分类,让我写个函数参考一下,当天晚上回去就开始,忙了四个多小时,终于写出来了,时间复杂度最小是n,最大是 2n-(一级分类的类别数量),经过测试运效率的确比递归算法高
<?php /** * 将无限分类的数据格式化成树的格式 * * @author Xuefen.Tong * @param array $items * @return array $tree */ function genTree($items){ $tree = array(); //格式化的树 /** * 定义树中的所有子孙节点所对应的键值 : * 如元素: array('id' => 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 '<div style="float:left;width:300px;overflow: visible;">'; echo "<pre>"; print_r($ar); echo "</pre>"; echo "</div>"; } /** * 以下这个类是从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 <= 0 || $this->getLayer($id) <= $layer)) { $options[$id] = $this->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),"<br/>"; echo "tree 类时间1:",($time4-$time3),", 时间2:",($time5-$time4),"<br/>"; div_print_r($tree1); div_print_r($tree2); div_print_r($Ctree2); div_print_r($Ctree1);
更多精彩
赞助商链接