无限分类数据格式化成树

无限分类是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 <= 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),"
";
 echo "tree　　 类时间1：",($time4-$time3),",  时间2：",($time5-$time4),"
";
 div_print_r($tree1);
 div_print_r($tree2);
 div_print_r($Ctree2);
 div_print_r($Ctree1);