在javascript中从平面数组构建树数组

我有一个复杂的json文件，我必须使用javascript来处理它，以便稍后构建一棵树。 json的每个条目都有：id：唯一标识，parentId：父节点的标识（如果节点是树的根，则为0）level：树中的深度级别

json数据已经“排序”了。 我的意思是一个条目将在其上方有一个父节点或兄弟节点，并且在它自己下面是一个子节点或一个兄弟节点。

输入：

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": null
        },
        {
            "id": "6",
            "parentId": "12",
            "text": "Boy",
            "level": "2",
            "children": null
        },
                {
            "id": "7",
            "parentId": "12",
            "text": "Other",
            "level": "2",
            "children": null
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children": null
        },
        {
            "id": "11",
            "parentId": "9",
            "text": "Girl",
            "level": "2",
            "children": null
        }
    ],
    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": null
        },
        {
            "id": "8",
            "parentId": "5",
            "text": "Puppy",
            "level": "2",
            "children": null
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": null
        },
        {
            "id": "14",
            "parentId": "13",
            "text": "Kitten",
            "level": "2",
            "children": null
        },
    ]
}

预期产出：

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": [
                {
                    "id": "6",
                    "parentId": "12",
                    "text": "Boy",
                    "level": "2",
                    "children": null
                },
                {
                    "id": "7",
                    "parentId": "12",
                    "text": "Other",
                    "level": "2",
                    "children": null
                }   
            ]
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children":
            {

                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": null
            }
        }

    ],    

    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": 
                {
                    "id": "8",
                    "parentId": "5",
                    "text": "Puppy",
                    "level": "2",
                    "children": null
                }
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": 
            {
                "id": "14",
                "parentId": "13",
                "text": "Kitten",
                "level": "2",
                "children": null
            }
        }

    ]
}

---

如果您使用地图查找，则有一个有效的解决方案。 如果父母总是来到他们的孩子面前，你可以合并两个for-loop。 它支持多个根。 它在悬挂分支上给出错误，但可以修改为忽略它们。 它不需要第三方库。 就我所知，它是最快的解决方案。

function list_to_tree(list) {
    var map = {}, node, roots = [], i;
    for (i = 0; i < list.length; i += 1) {
        map[list[i].id] = i; // initialize the map
        list[i].children = []; // initialize the children
    }
    for (i = 0; i < list.length; i += 1) {
        node = list[i];
        if (node.parentId !== "0") {
            // if you have dangling branches check that map[node.parentId] exists
            list[map[node.parentId]].children.push(node);
        } else {
            roots.push(node);
        }
    }
    return roots;
}

var entries = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1"
    }, { /*...*/ }
];

console.log(list_to_tree(entries));

如果你进入复杂性理论，这个解决方案是Θ（n log（n））。 递归滤波器解决方案是Θ（n ^ 2），这对于大数据集可能是个问题。

---

正如@Sander所提到的，@ Halcyon的答案假设了一个预先排序的数组，下面不会。 （但它假设你已经加载了underscore.js - 虽然它可以用香草写成javascript）：

码

unflatten = function( array, parent, tree ){

    tree = typeof tree !== 'undefined' ? tree : [];
    parent = typeof parent !== 'undefined' ? parent : { id: 0 };

    var children = _.filter( array, function(child){ return child.parentid == parent.id; });

    if( !_.isEmpty( children )  ){
        if( parent.id == 0 ){
           tree = children;   
        }else{
           parent['children'] = children;
        }
        _.each( children, function( child ){ unflatten( array, child ) } );                    
    }

    return tree;
}

要求

它假设属性'id'和'parentid'分别表示ID和父ID。 必须有父ID为0的元素，否则会返回空数组。 孤儿元素和他们的后代是'迷失'

用法示例

//Array to convert to tree structure.
var arr = [
        {'id':1 ,'parentid' : 0},
        {'id':2 ,'parentid' : 1},
        {'id':3 ,'parentid' : 1},
        {'id':4 ,'parentid' : 2},
        {'id':5 ,'parentid' : 0},
        {'id':6 ,'parentid' : 0},
        {'id':7 ,'parentid' : 4}
];
tree = unflatten( arr );

的jsfiddle

http://jsfiddle.net/LkkwH/1/

---

有同样的问题，但我不能确定数据是否排序 。 我不能使用第三方库，所以这只是香草Js; 输入数据可以从@ Stephen的例子中获得;

function unflatten(arr) {
  var tree = [],
      mappedArr = {},
      arrElem,
      mappedElem; 

  // First map the nodes of the array to an object -> create a hash table.
  for(var i = 0, len = arr.length; i < len; i++) {
    arrElem = arr[i];
    mappedArr[arrElem.id] = arrElem;
    mappedArr[arrElem.id]['children'] = [];
  }


  for (var id in mappedArr) {
    if (mappedArr.hasOwnProperty(id)) {
      mappedElem = mappedArr[id];
      // If the element is not at the root level, add it to its parent array of children.
      if (mappedElem.parentid) {
        mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
      }
      // If the element is at the root level, add it to first level elements array.
      else {
        tree.push(mappedElem);
      }
    }
  }
  return tree;
} 

JS小提琴

平面数组到树

链接地址: http://www.djcxy.com/p/30469.html

上一篇: Build tree array from flat array in javascript

下一篇: What is the most efficient way to get an ordered list from a Tree (Diagram)?