获取层级的级别

Question

我有一个对象数组，每个对象都有一个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 应该彼此相邻，而不是将同一父级的兄弟相邻放置，而是将两个级别为3的表亲放在一起。

- adardesign

---

你的根元素长什么样？ - Joe Coder

有一个根节点，假设它的 parentId 为 1（将是一个字符串）。 - adardesign

@JoeCoder，不，它将是随机顺序。 - adardesign

@ATOzTOA 根节点是 id:1，它不是数据的一部分。 - adardesign

我更新了描述以使其更清晰。感谢您的意见。 - adardesign

Answer 1

下面的代码示例可以在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);

输出:

注意

如果您更改输入顺序，排序结果会略有不同，但仍然是正确的（即按层次顺序，按兄弟分组）。

- Joe Coder

---

看起来很不错！有没有省略实际根目录的选项？（在您的数据中，它是第一个..） - adardesign

Answer 2

我不确定你从哪里获取level的值，所以我假设它只是一个整数。顺便说一下，你可以通过循环遍历数组并添加level属性到每个数组项中。

for (var i = 0, l = data.length; i < l; i++) { 
    data[i].level = i
}

这将提供

data = [{id:"1", parentId:"3", level:0 }, {id:"2", parentId:"1", level:1 } ...]

- Anthony

---

我希望通过循环遍历数组并确定层次结构来动态添加“level”，同时如我所指定的那样，“id”不会是整数，而是字符串。 - adardesign

所以你的意思是找出这个父元素中具有此ID的元素深度，并将其分配给level属性？ - Anthony

在上面的for循环中使用jQuery： data[i].level = $(data[i].id).parentsUntil($(data[i].parentId)).length + 1; - Anthony

@Mark Dee 谢谢，但是 id 和 parentId 不是整数，它们将是字符串。 - adardesign

Answer 3

这是您的工作代码。级别从2开始。

警告：如果无法计算级别，则应用程序可能会进入无限循环。因此，请确保parentId对于所有对象都是有效的，并且其中至少一个具有parentId="id-1"。

<script type="text/javascript">
    data = [
        {
            id:"id-2",
            parentId:"id-3"
        },
        {
            id:"id-4",
            parentId:"id-2"
        },
        {
            id:"id-3",
            parentId:"id-5"
        },
        {
            id:"id-5",
            parentId:"id-1"
        }
    ];

    function processData() {
        flag = true;

        while(flag) {
            flag = false;

            for(var i = 0; i < data.length; i++) {
                if(data[i].parentId == "id-1") {
                    data[i].level = 2;
                } else {
                    l = getLevel(data[i].parentId);
                    if(l > 0) {
                        data[i].level = l + 1;
                    } else {
                        flag = true;
                    }
                }
            }
        }
    }

    function getLevel(id) {
        for(var i = 0; i < data.length; i++) {
            if(data[i].id == id) {
                if(data[i].level) {
                    return data[i].level;
                } else {
                    return 0;
                }
            }
        }

        return 0;
    }

    processData();

    console.log(data);

</script>

- ATOzTOA

Answer 4

一种解决这个问题的方法是创建一个DOM层次结构，而无需使用递归。对于数组中的每个项目，创建一个div并将其附加到其父级上。然后遍历DOM并分配级别（顶部为级别1，然后为每个子级添加1）。

我在这里设置了一个简单的演示： http://jsfiddle.net/4AqgM/ 代码摘录：

top.dataset.level="1";
var topChildren=top.getElementsByTagName("div");
for (var i=0;i<topChildren.length;i++) {
topChildren[i].dataset.level=parseInt(topChildren[i].parentNode.dataset.level)+1;
}

- Christophe

---

@adardesign 抱歉，我不确定是否理解。这些 div 只是中间步骤，不打算保留。您的问题并未说明您想要任何（嵌套或非嵌套）div。 - Christophe

巧妙地将DOM用作数据结构的方式，但是这样做是多余的，因为树已经存在作为一系列“parentId”的引用。 - Joe Coder

@JoeCoder 对于冗余我表示同意。如果关卡的目的是构建DOM树(问题中未说明)，我的方法会很有趣。 - Christophe

@Christophe，正确的，目的是最终构建DOM，但不是嵌套式的，我将生成一个平面的DOM父级和子级旁边... - adardesign

@adardesign 我明白了。我稍微修改了我的演示，以便在最后取消嵌套的divs，希望这有所帮助：http://jsfiddle.net/4AqgM/3/。再次说明，这是粗糙的代码，还有优化的空间... - Christophe