PHP无限级分类数据格式化成树


PHP #无限级分类2012-10-29 14:40

无限分类是web开发中经常遇到的,比如文章分类,商品分类,用户权限的分类等等。传统的做法是用递归的算法进行,而我们知道,递归即费时间,又费空间。

以下是PHP实现的无限级分类数据格式化成树。

<?php 
/**
 * 将无限分类的数据格式化成树的格式
 *
 * @author Xuefen.Tong  http://yige.org/php/
 * @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);


相关文章

粤ICP备11097351号-1