[转]JavaScript将具有父子关系的原始数据格式化成树形结

前几天遇到一个树型组件（类似树形菜单）数据格式化的问题，由于后台把原始查询的数据直接返回给前端，父子关系并未构建，因此需要前端JS来完成，后台返回的数据和下面的测试数据相似。

var data=[
  {id:1,pid:0,text:'A'},
  {id:2,pid:4,text:"E[父C]"},
  {id:3,pid:7,text:"G[父F]"},
  {id:4,pid:1,text:"C[父A]"},
  {id:5,pid:6,text:"D[父B]"},
  {id:6,pid:0,text:'B'},
  {id:7,pid:4,text:"F[父C]"}
];

我们可以发现上面的测试数据有几个特点，父节点与子节点不是顺序排列的，也就是说按照id的顺序，并不是先有父节点，然后有下面的子节点，顺序是混乱的，再就是父子层级有很多，这里是3层。总结为：顺序混乱，层级未知。

如果是顺序排列，层级固定，可以投机取巧，写法相对简单，但是这里恰恰相反。因此给格式化造成了一定的困难，当遇到层级未知的时候，一般都会想到递归的写法，这里我感觉用递归也不好做，因此我也就没有向这方面去深入思考，这里就也不做多的说明。

那么我的做法比起递归来讲更容易理解，先看下代码。

function toTreeData(data){
    var pos={};
    var tree=[];
    var i=0;
    while(data.length!=0){
        if(data[i].pid==0){
            tree.push({   //顶层节点直接推入tree数组
                id:data[i].id,
                text:data[i].text,
                children:[]
            });
            pos[data[i].id]=[tree.length-1];  //顶层节点保存其所在路径数组，如 [0]
            data.splice(i,1);  //将当前数据从data移除
            i--;
        }else{
            var posArr=pos[data[i].pid];  //先获取当前节点的父节点位置数组, 如[0, 0, 0]
            if(posArr!=undefined){  //如果存在父节点位置信息
                var obj=tree[posArr[0]];  //父节点所在的顶层节点对象
                for(var j=1;j<posArr.length;j++){
                    obj=obj.children[posArr[j]];  //遍历找到tree中的父节点对象
                }
                obj.children.push({  //将当前对象插入到父节点的children里
                    id:data[i].id,
                    text:data[i].text,
                    children:[]
                });
                pos[data[i].id]=posArr.concat([obj.children.length-1]);  //依据父节点的位置数组去生成当前节点的位置信息
                data.splice(i,1);   //将当前对象从data中移除
                i--;
            }
        }
        i++;
        if(i>data.length-1){  //如果i大于data.length，从头开始继续遍历
            i=0;
        }
    }
    return tree;
}

前面的测试数据经过上面代码中的方法格式化后如下：

[
    {
        "id": 1,
        "text": "A",
        "children": [
            {
                "id": 4,
                "text": "C[父A]",
                "children": [
                    {
                        "id": 7,
                        "text": "F[父C]",
                        "children": [
                            {
                                "id": 3,
                                "text": "G[父F]",
                                "children": []
                            }
                        ]
                    },
                    {
                        "id": 2,
                        "text": "E[父C]",
                        "children": []
                    }
                ]
            }
        ]
    },
    {
        "id": 6,
        "text": "B",
        "children": [
            {
                "id": 5,
                "text": "D[父B]",
                "children": []
            }
        ]
    }
]

原理很简单，使用一个死循环来遍历数组，循环跳出的条件是数组的长度为0，也就是说，循环内部会引起数组长度的改变。这里就几个关键点做一下说明。

1. 为什么要用死循环？顺序混乱，如果单次循环，子节点出现在父节点之前，子节点不好处理，这里做一个死循环相当于先把父节点全部找出，但是这里又不是简单的先把所有的父节点找出，找的同时，如果这个节点父节点已经找到，那么可以继续做后续操作;
2. 如何建立层级关系？代码中有一个变量pos，这个用于保存每个已添加到tree中的节点在tree中位置信息，比如上面测试数据父节点A添加到tree后，那么pos中增加一条数据，pos={”1“:[0]}，1就是父节点A的id，这样写便于查找，[0]表示父节点A在tree的第一个元素，即tree[0]，如果某个位置信息为[1,2,3]，那么表示这个节点在tree[1].children[2].children[3]，这里的位置关系其实就是父子的层级关系。
   上面的测试数据的pos信息如下：

{
    "1":[0],
    "2":[0,0,1],
    "3":[0,0,0,0],
    "4":[0,0],
    "5":[1,0],
    "6":[1],
    "7":[0,0,0]
}