遍历树javascript [英] Traversing a tree javascript

问题描述

我正在尝试遍历JavaScript中的图形。我的工作是遍历并解析下图的所有可能结果。

I am trying to traverse a graph in javascript. My job is to traverse and parse all the possible outcomes of the following graph.

这就是我将图形存储在JS对象中的方式。

This is how I am storing the graph in a JS object.

var graph = {
    alpha: {
        in: [],
        out: ['a', 'b']
    },
    a: {
        in: ['alpha'],
        out: []
    },
    b: {
        in: ['alpha'],
        out: ['c', 'e']
    },
    c: {
        in: ['b'],
        out: ['d']
    },
    d: {
        in: ['c'],
        out: []
    },
    e: {
        in: ['b'],
        out: ['f', 'g']
    },
    f: {
        in: ['e'],
        out: []
    },
    g: {
        in: ['e'],
        out: []
    }
};

我需要解析它以获得以下输出。

I need to parse it to get the following output.

output = [
    ['alpha', 'a'],
    ['alpha', 'b', 'c', 'd'],
    ['alpha', 'b', 'e', 'f'],
    ['alpha', 'b', 'e', 'g']
];

要注意的主要事项是：

1. alpha 始终是父节点。


2. 任何节点只能有个输入连接，最大<< c $ c> n -输出连接数

1. alpha is always the parent node.
2. any node can have only one input connection and maximum of n-number of output connections

现在，我的方法是使用递归。没关系，我只是无法理解。有人可以帮我吗？

Right now my approach is to use recursion. BUt I just can't get my head around it. Can anyone give me a hand here?

var getChild = function (Obj) {

    if ( Obj['out'].length == 0){
        console.log('END');
        return
    }else{
        var shifted = Obj['out'].shift();
        console.log(shifted);
        return getChild(graph[shifted]);
    }

}

任何人都可以引导我穿越图以最有效的方式

Can anyone guide me to traverse the graph in maximum efficient way

推荐答案

您可以按照深度优先的方式遍历树，如下所示：

You could traverse your tree in a Depth First manner as follow:

var traverse = function(tree, current) {
    //process current node here

    //visit children of current
    for (var cki in current.out) {
        var ck = current.out[cki];
        var child = tree[ck];
        traverse(tree, child);
    }
}

//call on root node
traverse(graph, graph["alpha"]);

[edit：上面的错误]

[edit: mistake just above]

但是，树的平面布局有什么特殊原因吗？ JS允许您任意嵌套数据，因此您只需

However, is there any particular reason for the flat layout of the tree? JS allows you to nest data arbitrarily, so you could just have

 var graph = {
    alpha: {
        a: {},
        b: {
            c: {
                d: {}
            },
            e: {
                f: {},
                g: {}
            }
        }
    }
}

现在，您仅处理节点本身，不需要引用。这使得循环（将破坏上面的功能）成为不可能。
要遍历此树，可以将遍历功能简化为仅传递当前节点：

Now you are only dealing with the nodes themselves, and you don't need references. This makes loops (which would break the above function) impossible. To traverse this tree, you can simplify the traverse function to only passing the current node:

var traverse2 = function(current) {
    //process current node here
    console.log('visiting ' + current);

    //visit children of current
    for (var ck in current) {
        var child = current[ck];
        traverse2(child);
    }
}

//call on root node
traverse(graph);

这篇关于遍历树javascript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！