javascript - 用Js实现非递归无限分类

Question

自定义一组数据，内容任意，要求做到将无序的多级别数据格式化成数
这是boss给我出的一道题，他是PHP，而我还只是个js新手
之前以递归的形势完成了这道题，然后boss就让我再用非递归的办法做一次

以下是我自定义的数据，以层次编码的方式表述数据间的关系：
最终完成的效果是用数组嵌套，类似于:

var data=[
    {id:'01',name:"A"},
    {id:'0101',name:"A1"},
    {id:'0103',name:"A3"},
    {id:'0102',name:"A2"},
    {id:'0202',name:"B2"},    
    {id:'0301',name:"C1"},
    {id:'0303',name:"C3"},
    {id:'0302',name:"C2"},
    {id:'02',name:"B"},
    {id:'0201',name:"B1"},  
    {id:'020101',name:"B11"},
    {id:'030103',name:"C13"},
    {id:'03010301',name:"C131"},
    {id:'03010302',name:"C132"},
    {id:'0203',name:"B3"},
    {id:'03',name:"C"},
    {id:'030101',name:"C11"},
    {id:'030102',name:"C12"},  
    {id:'0301030101',name:"C1311"}, 
    {id:'0301030201',name:"C1321"}  
];

[
    [A,[A1,A2,A3]],
    [B,[B1,B2,B3]],
    [C,[
        C1,C2,C3,
            [C11,C12,C13
                [c131,c132]
            ]
        ]
    ]          
]    

或者其他能够把树表示清楚的格式也可以

这只是一个PHP的boss给我这个JS新人出的一道小考题
没有实际的用途，所以数据也是任意的，只要能达到效果就可以
只是我数据结构的知识实在太过贫乏，做了很久都无法达到效果
在网上查了很多资料，大多是关于php的无限极非递归实现，看起来很吃力，也没什么头绪

PS：下面简述一下我的思路：
1、 将同一级别的数据组成数组，放入group数组的对应位置，最后获取级别长度
2、 for循环由下至上，将子节点数据插入父节点的数组中，保存父节点，作为下次循环的子节点
最后在代码实现的过程中，卡在了当有多个子节点时，怎么确定各个父节点的位置，如

   [[B11],[C11,C12]]

B11需要插入到上一级的B数组中，并对应B1，而[C11，C12]需要插入到C数组中，并对应C1，如果到更深层次，要确定的位置量跟多，具体怎么实现，实在没有头绪，感觉我的思路应该不对

如果诸位有什么思路，或者能建议我去了解哪方面的资料，都可以说一说，感谢大家了！

Answer 1

因为第一次提问需要审核，在等审核的时候我把php的解决方案研究了一下
最后用JS模仿成功了，PHP方案代码如下：
http://www.oschina.net/code/s...

<?php
 
/**
 * 此方法由@Tonton 提供
 * http://my.oschina.net/u/918697
 * @date 2012-12-12 
 */
function genTree5($items) { 
    foreach ($items as $item) 
        $items[$item['pid']]['son'][$item['id']] = &$items[$item['id']]; 
    return isset($items[0]['son']) ? $items[0]['son'] : array(); 
} 
 
/**
 * 将数据格式化成树形结构
 * @author Xuefen.Tong
 * @param array $items
 * @return array 
 */
function genTree9($items) {
    $tree = array(); //格式化好的树
    foreach ($items as $item)
        if (isset($items[$item['pid']]))
            $items[$item['pid']]['son'][] = &$items[$item['id']];
        else
            $tree[] = &$items[$item['id']];
    return $tree;
}
 
$items = array(
    1 => array('id' => 1, 'pid' => 0, 'name' => '江西省'),
    2 => array('id' => 2, 'pid' => 0, 'name' => '黑龙江省'),
    3 => array('id' => 3, 'pid' => 1, 'name' => '南昌市'),
    4 => array('id' => 4, 'pid' => 2, 'name' => '哈尔滨市'),
    5 => array('id' => 5, 'pid' => 2, 'name' => '鸡西市'),
    6 => array('id' => 6, 'pid' => 4, 'name' => '香坊区'),
    7 => array('id' => 7, 'pid' => 4, 'name' => '南岗区'),
    8 => array('id' => 8, 'pid' => 6, 'name' => '和兴路'),
    9 => array('id' => 9, 'pid' => 7, 'name' => '西大直街'),
    10 => array('id' => 10, 'pid' => 8, 'name' => '东北林业大学'),
    11 => array('id' => 11, 'pid' => 9, 'name' => '哈尔滨工业大学'),
    12 => array('id' => 12, 'pid' => 8, 'name' => '哈尔滨师范大学'),
    13 => array('id' => 13, 'pid' => 1, 'name' => '赣州市'),
    14 => array('id' => 14, 'pid' => 13, 'name' => '赣县'),
    15 => array('id' => 15, 'pid' => 13, 'name' => '于都县'),
    16 => array('id' => 16, 'pid' => 14, 'name' => '茅店镇'),
    17 => array('id' => 17, 'pid' => 14, 'name' => '大田乡'),
    18 => array('id' => 18, 'pid' => 16, 'name' => '义源村'),
    19 => array('id' => 19, 'pid' => 16, 'name' => '上坝村'),
);
echo "<pre>";
print_r(genTree5($items));
print_r(genTree9($items));
 

我的模仿如下：

var data=[
    {id:1,pId:0,cId:1,name:"A"},
    {id:11,pId:1,cId:1,name:"A1"},
    {id:12,pId:1,cId:2,name:"A2"},
    {id:13,pId:1,cId:3,name:"A3"},
    {id:22,pId:2,cId:2,name:"B2"},    
    {id:31,pId:3,cId:1,name:"C1"},
    {id:32,pId:3,cId:2,name:"C2"},
    {id:33,pId:3,cId:3,name:"C3"},
    {id:2,pId:0,cId:2,name:"B"},
    {id:21,pId:2,cId:1,name:"B1"},  
    {id:36,pId:31,cId:3,name:"C13"},
    {id:37,pId:36,cId:1,name:"C131"},
    {id:23,pId:2,cId:3,name:"B3"},
    {id:3,pId:0,cId:3,name:"C"},
    {id:34,pId:31,cId:1,name:"C11"},
    {id:35,pId:31,cId:2,name:"C12"},  
    {id:38,pId:37,cId:1,name:"C1311"}   
];
function treeMenu(tree){
    var newTree = [];
    var tmp = [];
    var item = [];
    //遍历数组，建立临时扁平数据
    for(var x in tree){
        item[tree[x].id] = [tree[x].name];
    }
    //遍历数组，同时获取每个对象的父节点和子节点数据
    for(var x in tree){
        var parentId = tree[x].pId; 
        var childId = tree[x].cId;
        //该对象的父元素节点在临时数据中的对应位置有数据存在时
        //说明这是一个二级以上的节点
        //将它的数据传递给父节点对应的子节点位置
        if(item[parentId]){
            item[parentId][childId] = item[tree[x].id];
        }
        //如果没有，说明这是一个一级节点，直接传递给最终结果
        else{
            newTree.push(item[tree[x].id]);
        }
        //因为传递的值为引用值，所以当处理数据时
        //对子节点进行操作后,同样会反映到父节点中，最后体现在最终结果里        
    }
    item = null; // 解除临时数据
    return newTree;
}
console.log(treeMenu(data));

最后达到了预期要求，如果大家对这个有兴趣，欢迎来提提意见建议！