遍历树javascript

Question

我试图在javascript中遍历图表.我的工作是遍历和解析下图的所有可能结果.

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

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: []
    }
};

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

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

需要注意的关键事项是:

1. alpha 始终是父节点.
2. 任何节点只能有one输入连接和最多数量n的输出连接

现在我的方法是使用递归.我只是无法理解它.任何人都可以帮我一把吗？

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]);
    }

}

任何人都可以指导我以最有效的方式遍历图表

Answer 1

您可以按照Depth First方式遍历树,如下所示:

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"]);

[编辑:上面的错误]

但是,树的平面布局有什么特别的原因吗？JS允许您任意嵌套数据,因此您可以拥有

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

现在您只处理节点本身,并且您不需要引用.这使得循环(这将破坏上述功能)变得不可能.要遍历此树,可以将遍历功能简化为仅传递当前节点:

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);