我有一个复杂的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),这对于大型数据集可能是一个问题。

其他回答

经过多次尝试,我得出了这个结论:

const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent).map(child => ({ ...child, children: arrayToTree(arr, child.index) }));

   

const entries = [ { index: 1, parent: 0 }, { index: 2, parent: 1 }, { index: 3, parent: 2 }, { index: 4, parent: 2 }, { index: 5, parent: 4 }, { index: 6, parent: 5 }, { index: 7, parent: 6 }, { index: 8, parent: 7 }, { index: 9, parent: 8 }, { index: 10, parent: 9 }, { index: 11, parent: 7 }, { index: 13, parent: 11 }, { index: 12, parent: 0 } ]; const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent) .map(child => ({ ...child, children: arrayToTree(arr, child.index) })); console.log(arrayToTree(entries));

下面是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);

将节点数组转换为树

ES6函数转换数组节点(由父ID相关)到树结构:

/**
 * Convert nodes list related by parent ID - to tree.
 * @syntax getTree(nodesArray [, rootID [, propertyName]])
 *
 * @param {Array} arr   Array of nodes
 * @param {integer} id  Defaults to 0
 * @param {string} p    Property name. Defaults to "parent_id"
 * @returns {Object}    Nodes tree
 */

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {

  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes= [];
  if (o[n.id].nodes) n.nodes= o[n.id].nodes;

  o[n[p]].nodes.push(n);
  o[n.id] = n;

  return o;
}, {});

从节点树生成HTML列表

有了我们的树,这里有一个递归函数来构建UL > LI元素:

/**
 * Convert Tree structure to UL>LI and append to Element
 * @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
 *
 * @param {Array} tree Tree array of nodes
 * @param {Element} el HTMLElement to insert into
 * @param {function} cb Callback function called on every LI creation
 */

const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');

  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);

  ul.append(li);
  return ul;
}, document.createElement('ul')));

演示时间

下面是一个使用上述两个函数的线性节点数组的例子:

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => { if (!o[n.id]) o[n.id] = {}; if (!o[n[p]]) o[n[p]] = {}; if (!o[n[p]].nodes) o[n[p]].nodes = []; if (o[n.id].nodes) n.nodes = o[n.id].nodes; o[n[p]].nodes.push(n); o[n.id] = n; return o; }, {}); const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => { const li = document.createElement('li'); if (cb) cb.call(li, n); if (n.nodes?.length) treeToHTML(n.nodes, li, cb); ul.append(li); return ul; }, document.createElement('ul'))); // DEMO TIME: const nodesList = [ {id: 10, parent_id: 4, text: "Item 10"}, // PS: Order does not matters {id: 1, parent_id: 0, text: "Item 1"}, {id: 4, parent_id: 0, text: "Item 4"}, {id: 3, parent_id: 5, text: "Item 3"}, {id: 5, parent_id: 4, text: "Item 5"}, {id: 2, parent_id: 1, text: "Item 2"}, ]; const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0) treeToHTML(myTree, document.querySelector("#tree"), function(node) { this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`; this._node = node; this.addEventListener('click', clickHandler); }); function clickHandler(ev) { if (ev.target !== this) return; console.clear(); console.log(this._node.id); }; <div id="tree"></div>

我的typescript解决方案,可能对你有帮助:

type ITreeItem<T> = T & {
    children: ITreeItem<T>[],
};

type IItemKey = string | number;

function createTree<T>(
    flatList: T[],
    idKey: IItemKey,
    parentKey: IItemKey,
): ITreeItem<T>[] {
    const tree: ITreeItem<T>[] = [];

    // hash table.
    const mappedArr = {};
    flatList.forEach(el => {
        const elId: IItemKey = el[idKey];

        mappedArr[elId] = el;
        mappedArr[elId].children = [];
    });

    // also you can use Object.values(mappedArr).forEach(...
    // but if you have element which was nested more than one time
    // you should iterate flatList again:
    flatList.forEach((elem: ITreeItem<T>) => {
        const mappedElem = mappedArr[elem[idKey]];

        if (elem[parentKey]) {
            mappedArr[elem[parentKey]].children.push(elem);
        } else {
            tree.push(mappedElem);
        }
    });

    return tree;
}

用法示例:

createTree(yourListData, 'id', 'parentId');

如果使用地图查找,就有一个有效的解决方案。如果父母总是在他们的孩子之前,你可以合并两个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),这对于大型数据集可能是一个问题。