如何递归地构建树中每个节点的路径 - JavaScript? [英] How to build the path to each node in a tree recursively - JavaScript?

问题描述

我的数据结构如下:

var tree = [
    {
        id: 1,
        children: []
    }, {
        id: 2,
        children: [
            {
                id: 3,
                children: []
            }
        ]
    }
];

一个分支上可以有任意数量的节点或子节点.

There can be any number of nodes or children on one branch.

我的目标是为每个节点建立一条路径.

My goal is to build a path to every node.

例如 id: 3 的路径为 1 > 2 > 3id: 2 的路径为 1 > 2

For example id: 3 will have a path of 1 > 2 > 3 id: 2 will have a path of 1 > 2

我想通过算法运行我的树，所以它会像这样修改:

I want to run my tree through the algorithm so it will be modified like this:

 var tree = [
        {
            id: 1,
            path: [1],
            children: []
        }, {
            id: 2,
            path: [2],
            children: [
                {
                    id: 3,
                    path: [2, 3],
                    children: []
                }
            ]
        }
    ];

我编写了一个算法来访问树中的所有节点:https://plnkr.co/edit/CF1VNofzpafhd1MOMVfj

I have written an algorithm that will visit all of the nodes in the tree: https://plnkr.co/edit/CF1VNofzpafhd1MOMVfj

如何构建每个节点的路径?

How can I build the path to each node?

这是我的尝试:

function traverse(branch, parent) {

  for (var i = 0; i < branch.length; i++) {

    branch[i].visited = true;

    if (branch[i].path === undefined) {
      branch[i].path = [];
    }

    if (parent != null) {
      branch[i].path.push(parent);
    }

    if (branch[i].children.length > 0) {
      traverse(branch[i].children, branch[i].id);
    }

  }

}

推荐答案

除了不直接涉及的父级的不明确获取之外，您可以将路径存储为数组并为每个嵌套迭代获取它.

Beside the unclear taking of not directly involved parents, you could store the path as arrray and take it for each nested iteration.

function iter(path) {
    path = path || [];
    return function (o) {
        o.path = path.concat(o.id);
        if (o.children) {
            o.children.forEach(iter(o.path));
        }
    }
}

var tree = [{ id: 1, children: [] }, { id: 2, children: [{ id: 3, children: [] }] }];

tree.forEach(iter());
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

这篇关于如何递归地构建树中每个节点的路径 - JavaScript?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！