算法苦逼，求一个最佳方案

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4366 天前的主题，其中的信息可能已经有所发展或是发生改变。

是关于php和mysql的。

从一个items里读出多条记录，字段为 id, title,parent_id。其中parent_id关联其他记录的id，如果没有关联parent_id默认为0。比如如下几条记录：

id title parent_id
1 title1 0
2 title2 0
3 title3 1
4 title4 2

请问如何最优雅的转化成这种json格式：

[
{id:1, title:title1, parent_id:0, child:[{id:3,title:title3,parent_id:1}]}
{id:2, title:title2, parent_id:0, child:[{id:4,title:title4,parent_id:2}]}
]

其实就是把子条目塞进父条目里，我的想法是要用两个循环先把父条目读出，然后再循环子条目塞进父条目里。哪位大神能用一个循环解决掉？

parent

title

21 条回复 • 1970-01-01 08:00:00 +08:00

talentsnail

2012-12-17 13:03:33 +08:00

$result = mysql_query("SELECT * FROM iterms");
while ( $one = mysql_fetch_array($result) ) {
if ($one['parent_id'] == 0){
创建一个新条目；
}
else {
把该条目添加到 id == $one['parent_id']的条目；
}
}

哈哈，刚刚开始学编程，所以，大神别笑^_^

Brutal

2012-12-17 13:12:52 +08:00

http://gist.github.com/4315906

可能有误，好久没写 PHP 了

iloveyou

2012-12-17 13:20:05 +08:00

@talentsnail
@Brutal
你两的方法差不多，其实这种我也想过，但是遇到点其他问题，所以弄成两个循环

Brutal

2012-12-17 13:21:14 +08:00

@iloveyou 什么问题？

iloveyou

2012-12-17 13:37:00 +08:00

主要是格式化的问题

halida

2012-12-17 13:47:53 +08:00

我还以为是算法时间优化嘞，原来只是语法层面的。。。

enj0y

2012-12-17 13:52:00 +08:00

后面使用$json_data=json_encode($array)即可将数组转换成json数据。

isy

2012-12-17 14:06:01 +08:00

@iloveyou 组织好 array 再用 josn_encode 不行么？

iloveyou

2012-12-17 14:10:28 +08:00

@halida 是啊不入大神们的法眼

@isy 是啊可以

iloveyou

2012-12-17 21:01:45 +08:00

@talentsnail
@Brutal

想的太简单了，如果子项先被循环怎么办？

lychee

2012-12-17 21:45:04 +08:00

@iloveyou 想的太复杂了，加上order by "parent_id" ASC 不就行了

iloveyou

2012-12-17 22:33:33 +08:00

@lychee 那要是我有其他排序呢，不是被打乱了？

aveline

2012-12-17 22:48:11 +08:00

举个栗子...

https://gist.github.com/e4cf4feea0faeddc2c06

aveline

2012-12-17 22:48:21 +08:00

http://gist.github.com/e4cf4feea0faeddc2c06

aveline

2012-12-17 22:49:22 +08:00

Gist 不能发了么...

gist.github.com/e4cf4feea0faeddc2c06

iloveyou

2012-12-17 22:59:31 +08:00

@aveline 好的明天我看看

iloveyou

2012-12-18 08:22:26 +08:00

@aveline 你这个也不行，你只提取parent_id为相同的一条

Just1n

2012-12-18 09:40:36 +08:00

可以在数据库里加两个字段（如果可以动数据库的话，并且表确实是一个严格的树形）：Lft,Rgt，都为int型。
记录如下：
id title parent_id Lft Rgt
0 title0 null 1 10
1 title1 0 2 5
2 title2 0 6 9
3 title3 1 3 4
4 title4 2 7 8

最底层节点永远是 Rgt-Lft==1
顶层节点永远是Lft==1
节点X的所有父节点为（假定目标节点为D）：
D.Lft < X.Lft && D.Rgt > X.Rgt
节点X的所有子节点为（假定目标节点为D）：
D.Lft > X.Lft && D.Rgt < X.Rgt

这样做的好处是，我只需要在更新表的时候做一次递归处理即可，其他时间无需递归，当然逻辑也比较清晰。

iloveyou

2012-12-18 11:48:49 +08:00

@Just1n 晕啊看着好高级啊，眼花。。。这是某种经典的算法吗？

Just1n

2012-12-18 11:52:29 +08:00

@iloveyou 经不经典我还真不知道，因为我是属于半路出家，对数学算法数据结构也是菜。以上只是我以前遇到的组织架构的处理方案。

sallon88

2012-12-19 16:12:53 +08:00

不就是无限分类么，曾经看到过有人使用引用做的，大概是这个样子
<pre>
function get_tree($items)
{
$tree = array(); //格式化好的树
foreach ($items as $item)
if (isset($items[$item['parent_id']]))
$items[$item['parent_id']]['child'][] = &$items[$item['id']];
else
$tree[] = &$items[$item['id']];
return $tree;
}
$items = array(
1 => array('id'=>1, 'title'=>'title1', 'parent_id'=>0),
2 => array('id'=>2, 'title'=>'title2', 'parent_id'=>0),
3 => array('id'=>3, 'title'=>'title3', 'parent_id'=>1),
4 => array('id'=>4, 'title'=>'title4', 'parent_id'=>2)
);
echo json_encode(get_tree($items));
</pre>