我有一个复杂的json文件,我必须处理javascript使其分层,以便稍后构建树。 json的每个条目都有: Id:唯一的Id, parentId:父节点的id(如果节点是树的根,则为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循环。它支持多个根。它在悬垂的分支上给出一个错误,但可以修改为忽略它们。它不需要第三方库。就我所知,这是最快的解决方法。

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", "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 } ]; console.log(list_to_tree(entries));

如果你喜欢复杂性理论,这个解决方案是Θ(n log(n))。递归过滤器的解决方案是Θ(n^2),这对于大型数据集可能是一个问题。

其他回答

类似问题的答案:

https://stackoverflow.com/a/61575152/7388356

更新

你可以使用ES6中引入的Map对象。基本上,你不再通过遍历数组来寻找父元素,你只需要从数组中通过父元素的id来获取父元素就像你在数组中通过索引来获取元素一样。

下面是一个简单的例子:

const 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
  }
];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.id, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.parentId !== "0") {
      let parentItem = arrMap.get(item.parentId);

      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

let tree = toTree(people);

console.log(tree);

也可以使用lodashjs(v4.x)

function buildTree(arr){
  var a=_.keyBy(arr, 'id')
  return _
   .chain(arr)
   .groupBy('parentId')
   .forEach(function(v,k){ 
     k!='0' && (a[k].children=(a[k].children||[]).concat(v));
   })
   .result('0')
   .value();
}

它可能是有用的包列表到树 安装:

bower install list-to-tree --save

or

npm install list-to-tree --save

例如,有列表:

var list = [
  {
    id: 1,
    parent: 0
  }, {
    id: 2,
    parent: 1
  }, {
    id: 3,
    parent: 1
  }, {
    id: 4,
    parent: 2
  }, {
    id: 5,
    parent: 2
  }, {
    id: 6,
    parent: 0
  }, {
    id: 7,
    parent: 0
  }, {
    id: 8,
    parent: 7
  }, {
    id: 9,
    parent: 8
  }, {
    id: 10,
    parent: 0
  }
];

使用包列表到树:

var ltt = new LTT(list, {
  key_id: 'id',
  key_parent: 'parent'
});
var tree = ltt.GetTree();

结果:

[{
  "id": 1,
  "parent": 0,
  "child": [
    {
      "id": 2,
      "parent": 1,
      "child": [
        {
          "id": 4,
          "parent": 2
        }, {
          "id": 5, "parent": 2
        }
      ]
    },
    {
      "id": 3,
      "parent": 1
    }
  ]
}, {
  "id": 6,
  "parent": 0
}, {
  "id": 7,
  "parent": 0,
  "child": [
    {
      "id": 8,
      "parent": 7,
      "child": [
        {
          "id": 9,
          "parent": 8
        }
      ]
    }
  ]
}, {
  "id": 10,
  "parent": 0
}];

这是上面的一个修改版本,适用于多个根项,我使用guid为我的id和parentid,所以在创建它们的UI中,我硬编码根项为0000000-00000-00000-TREE-ROOT-ITEM

var树= unflatten(记录," tree - root - item ");

function unflatten(records, rootCategoryId, parent, tree){
    if(!_.isArray(tree)){
        tree = [];
        _.each(records, function(rec){
            if(rec.parentId.indexOf(rootCategoryId)>=0){        // change this line to compare a root id
            //if(rec.parentId == 0 || rec.parentId == null){    // example for 0 or null
                var tmp = angular.copy(rec);
                tmp.children = _.filter(records, function(r){
                    return r.parentId == tmp.id;
                });
                tree.push(tmp);
                //console.log(tree);
                _.each(tmp.children, function(child){
                    return unflatten(records, rootCategoryId, child, tree);
                });
            }
        });
    }
    else{
        if(parent){
            parent.children = _.filter(records, function(r){
                return r.parentId == parent.id;
            });
            _.each(parent.children, function(child){
                return unflatten(records, rootCategoryId, child, tree);
            });
        }
    }
    return tree;
}

下面是Steven Harris的一个修改版本,它是普通的ES5,返回一个以id为键的对象,而不是返回顶层和子层的节点数组。

unflattenToObject = function(array, parent) {
  var tree = {};
  parent = typeof parent !== 'undefined' ? parent : {id: 0};

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

  if (childrenArray.length > 0) {
    var childrenObject = {};
    // Transform children into a hash/object keyed on token
    childrenArray.forEach(function(child) {
      childrenObject[child.id] = child;
    });
    if (parent.id == 0) {
      tree = childrenObject;
    } else {
      parent['children'] = childrenObject;
    }
    childrenArray.forEach(function(child) {
      unflattenToObject(array, child);
    })
  }

  return tree;
};

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 = unflattenToObject(arr);