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