我有一个对象数组，其中每个对象都有一个 id 和一个 ParentId 属性(因此它们可以排列在树中)。它们没有特定的顺序。

请注意，id 和 parentId 不会是整数，它们将是字符串(只是想让示例代码更清晰..)

只有一个根:假设它的 id:1 数据如下所示:

 data = [
   {
        id:"id-2",
        parentId:"id-3"
    },
    {
        id:"id-4",
        parentId:"2"
    },
    {
        id:"id-3",
        parentId:"id-4"
    },
    {
        id:"id-5",
        parentId:"id-4"
    },
    {
        id:"id-6",
        parentId:"id-1"
    },
    {
        id:"id-7",
        parentId:"id-1"
    }
    // and so on...
]

我正在寻找一种有效的方法来为每个对象提供一个 level 属性，该属性应该指定它的嵌套级别......

它们应该看起来像这样:

data = [
    {
        id:"id-2",
        parentId:"id-1",
        level:2
    },
    {
        id:"id-3",
        parentId:"id-4",
        level:5

    },
    {
        id:"id-4",
        parentId:"id-2",
        level:3

    },
    {
        id:"id-5",
        parentId:"id-4",
        level:5
    },
    {
        id:"id-6",
        parentId:"id-1",
        level:2

    },
    {
        id:"id-7",
        parentId:"id-3",
        level:4
    }
    // and so on...
]

简而言之:

我希望通过遍历数组并确定层次结构来动态添加 level..

此外，(如果可能的话)它们应该按照顺序排序，例如来自同一父级的所有对象 level:3 应该彼此相邻，而不是在那里应该是彼此相邻的同一 parent 的 sibling ，而不是彼此相邻的两个 3 级堂 sibling 。

最佳答案

以下代码的工作示例在 jsFiddle 上.

按 id 索引树并从每个节点向上遍历它，然后计数直到找到根。通过首先索引，我们接近 O(n) 时间复杂度(取决于树密度)。 ****更新以满足排序要求，并允许排除根节点***:

function levelAndSort(data, startingLevel) {
    // indexes
    var indexed = {};        // the original values
    var nodeIndex = {};      // tree nodes
    var i;
    for (i = 0; i < data.length; i++) {
        var id = data[i].id;
        var node = {
            id: id,
            level: startingLevel,
            children: [],
            sorted: false
        };
        indexed[id] = data[i];
        nodeIndex[id] = node;
    }

    // populate tree
    for (i = 0; i < data.length; i++) {
        var node = nodeIndex[data[i].id];
        var pNode = node;
        var j;
        var nextId = indexed[pNode.id].parentId;
        for (j = 0; nextId in nodeIndex; j++) {
            pNode = nodeIndex[nextId];
            if (j == 0) {
                pNode.children.push(node.id);
            }
            node.level++;
            nextId = indexed[pNode.id].parentId;
        }
    }

    // extract nodes and sort-by-level
    var nodes = [];
    for (var key in nodeIndex) {
        nodes.push(nodeIndex[key]);
    }
    nodes.sort(function(a, b) {
        return a.level - b.level;
    });

    // refine the sort: group-by-siblings
    var retval = [];
    for (i = 0; i < nodes.length; i++) {
        var node = nodes[i];
        var parentId = indexed[node.id].parentId;
        if (parentId in indexed) {
            var pNode = nodeIndex[parentId];
            var j;
            for (j = 0; j < pNode.children.length; j++) {
                var child = nodeIndex[pNode.children[j]];
                if (!child.sorted) {
                    indexed[child.id].level = child.level;
                    retval.push(indexed[child.id]);
                    child.sorted = true;
                }
            }
        }
        else if (!node.sorted) {
            indexed[node.id].level = node.level;
            retval.push(indexed[node.id]);
            node.sorted = true;
        }
    }
    return retval;
}

示例:

// level 0 (root) excluded
var startingLevel = 1;
var someData = [
    {id : "id-1", parentId : "id-0"},
    {id : "id-2", parentId : "id-0"},
    {id : "id-3", parentId : "id-2"},
    {id : "id-4", parentId : "id-3"},
    {id : "id-5", parentId : "id-4"},
    {id : "id-6", parentId : "id-4"},
    {id : "id-7", parentId : "id-0"},
    {id : "id-8", parentId : "id-1"},
    {id : "id-9", parentId : "id-7"},
    {id : "id-10", parentId : "id-1"},
    {id : "id-11", parentId : "id-1"},
    {id : "id-12", parentId : "id-1"}
];
var outputArray = levelAndSort(someData, startingLevel);

输出:

注意事项

如果您更改输入顺序，排序结果会略有不同，但仍然是正确的(即，按级别顺序，按兄弟分组)。

关于javascript - 获取层次结构的级别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14132831/