PHP-如何快速把一个表以左右节点结构存储无限级分类的数据转换成树状数组？

Question

Answer 1

最简单的方法便是 直接写
按照自左向右的顺序 可以简化 id
树中没有id 却能从树的节点顺序计算出id
定一个 节点结构体 包括name lft rgt
首先看到你在 表中的项有lft rgt 根本不是所说的左右子树节点 只是 节点中的元素
因为 他跟其他节点数据没有任何关系 所以也不可能有任何牵连
节点结构必然为 包含 name lft rgt的结构体
至于如何生成树
那就在简单不过了 在节点结构体中定义两个指针 分别是节点结构体的指针 用来指向左右子树
通过读表 一点点把它加入到树中 如此而已

Answer 2

自己先贴一个递归处理的方法

/**
* 先把查询出的结果创建成一条数组按照自己的左右节点为key自己本身为值
*/
function buildChainList($list){
$ChainList = array();
foreach ($list as $val){
$ChainList[$val['lft']-1] = $val;
$ChainList[$val['rgt']-1] = $val;
}
//给创建的数组按照key排序
ksort($ChainList);
return $ChainList;
}
/**
* 这个方法就是递归处理这条链上的节点
*/
function buildDomainArrayTree(&$param) {
if (!$param) return null;
$Node = array();
$i= key($param);
end($param);
$length= key($param);

while($i<=$length){

$current = $param[$i];
$len = $current['rgt'] - $current['lft'] - 1;

$Node[]= array('Current'=>$current
,'Children'=>buildDomainArrayTree(array_slice($param,$i+1,$len,true))
);
$i += ($len + 2);
}
return $Node;
}

$list = array(array('id'=>1,'name'=>'A','lft'=>1,'rgt'=>14)
,array('id'=>2,'name'=>'B','lft'=>2,'rgt'=>7)
,array('id'=>3,'name'=>'C','lft'=>8,'rgt'=>13)
,array('id'=>4,'name'=>'D','lft'=>3,'rgt'=>4)
,array('id'=>5,'name'=>'E','lft'=>5,'rgt'=>6)
,array('id'=>6,'name'=>'F','lft'=>9,'rgt'=>10)
,array('id'=>7,'name'=>'G','lft'=>11,'rgt'=>12)
);
$list = buildChainList($list);

$rs = buildDomainArrayTree($list);

var_dump($rs);

Answer 3

$data = mysql_....;
if($data === false || !isset($data))
exit;
$parents = array(); //记录每一层根的栈
$currentNode = array('children'=>array()); //整棵树的根（注意不是第一个节点，第一个节点会是它的第一个子节点）
$currentRight = 100000000; //保证这个数大于最大的右值，如果从1开始的连续节点，那也就是节点数的两倍。
foreach($data as $d)
{
while($d['lft'] > $currentRight)
{
//新节点不在当前节点内部
//出栈
$pvalue = array_pop($parents);
$pnode = $pvalue['node'];
$pnode['children'][$currentNode['id']] = $currentNode; //换成&$currentNode 使用引用也可以。不想要以id为索引的话，用[]=也可以
$currentNode = $pnode;
$currentRight = $pvalue['right'];
unset($pnode);
unset($pvalue);
}
//新节点在当前节点的内部
//保存当前节点
$parents[] = array('node'=>&$currentNode,'right'=>$currentRight);
$currentNode = array('id'=>$d['id'],'name'=>$d['name'],'children'=>array()); //要不要children分组依个人喜好，把子节点单组列出来遍历的时候比较方便，不用排除掉id和name
$currentRight = $d['rgt'];
}
while(count($parent) > 0)
{
//出栈
$pvalue = array_pop($parents);
$pnode = $pvalue['node'];
$pnode['children'][$currentNode['id']] = $currentNode; //换成&$currentNode 使用引用也可以。不想要以id为索引的话，用[]=也可以
$currentNode = $pnode;
$currentRight = $pvalue['right'];
unset($pnode);
unset($pvalue);
}
$root = $currentNode;
//如果需要第一个节点作为根：
$realroot = array_shift($root['children']);

不考虑PHP内部可能的复制（全用引用）的话，复杂度为O(n)