javascript - 通过递归遍历 Javascript 对象来累积路径

Question

我有一个存储在 Javascript 对象中的树结构，我想提取从 head(sms_in) 节点到分支中最后一个节点的所有可能路径。以下是树结构的示例表示。

注意:任何给定节点都可以有 n 个输出('true' 类型)连接，但只有一个输入连接。我的意思是，当您想从 sms_in 节点转到 isEmpty1 节点时，只有一条路径 [{ 'sms_in' : 'true' } ] 。但是，如果您想从 isEmpty1 转到 dbInsert1，则必须选择“false”路径，而不是“true” >' 路径。您也可以从 isEmpty 节点转到其他一些节点(在给定的情况下不是)。但是您只能从一条路径到达 isEmpty 节点，即通过“sms_in”节点。

    var graph =
{
    "metadata": {"id": "sms_in", "type": "api", "optionsDivId": "div_sms_in", "options": {}},
    "data": {
        "true": {
            "isEmpty1": {
                "metadata": {
                    "id": "isEmpty1",
                    "type": "empty",
                    "optionsDivId": "div_isEmpty1",
                    "options": {}
                },
                "data": {
                    "true": {
                        "sms1": {
                            "metadata": {
                                "id": "sms1",
                                "type": "api",
                                "optionsDivId": "div_sms1",
                                "options": {}
                            }, "data": {"true": {}, "false": false}
                        }
                    },
                    "false": {
                        "dbInsert1": {
                            "metadata": {
                                "id": "dbInsert1",
                                "type": "dbInsert",
                                "optionsDivId": "div_dbInsert1",
                                "options": {}
                            },
                            "data": {
                                "true": {
                                    "sms2": {
                                        "metadata": {
                                            "id": "sms2",
                                            "type": "api",
                                            "optionsDivId": "div_sms2",
                                            "options": {}
                                        }, "data": {"true": {}, "false": false}
                                    }
                                }, "false": false
                            }
                        }
                    }
                }
            }
        }, "false": false
    }
};

这里我有两种类型的节点，其中 'if/empty' 类型的节点有 'true/false' 类型的子节点，而所有其他节点只有'true' 类型节点。我想通过以下方式遍历节点并获取所有可能情况的完整路径。

var output = [

 [ {'sms_in':'true'}, {'isEmpty1':'true'}, {'sms1':''}],
 [{'sms_in':'true'}, {'isEmpty1':'false'}, {'dbInsert1':'true'}, {'sms2':''}]

];

我可以遍历树，但我不知道如何累积完整路径以获取数组格式的输出。有人可以帮我吗？

Answer 1

这个解决方案有效，但我不会依赖它，因为数据结构。

基本上你有这样的结构

data.true[k].data.true  --> { k: true }
data.true[k].data.false --> { k: false }
          ^   and   ^

这很不常见。

但是 sms1 和 sms2 的值在我的例子中是 true 而不是 ''。所需的值不在给定的对象中。

function traverse(o, p, last) {
    var r = [];
    Object.keys(o).forEach(function (k) {
        var l = typeof o[k] === 'object' && Object.keys(o[k])[0],
            temp = {};
        temp[last] = k;
        if (l && o[k][l].data && typeof o[k][l].data === 'object') {
            r = r.concat(traverse(o[k][l].data, p.concat(temp), l));
        } else {
            o[k] && r.push(p.concat(temp));
        }
    });
    return r;
}

var graph = { "metadata": { "id": "sms_in", "type": "api", "optionsDivId": "div_sms_in", "options": {} }, "data": { "true": { "isEmpty1": { "metadata": { "id": "isEmpty1", "type": "empty", "optionsDivId": "div_isEmpty1", "options": {} }, "data": { "true": { "sms1": { "metadata": { "id": "sms1", "type": "api", "optionsDivId": "div_sms1", "options": {} }, "data": { "true": {}, "false": false } } }, "false": { "dbInsert1": { "metadata": { "id": "dbInsert1", "type": "dbInsert", "optionsDivId": "div_dbInsert1", "options": {} }, "data": { "true": { "sms2": { "metadata": { "id": "sms2", "type": "api", "optionsDivId": "div_sms2", "options": {} }, "data": { "true": {}, "false": false } } }, "false": false } } } } } }, "false": false } },
    path = traverse(graph.data, [], 'sms_in');

document.write('<pre>' + JSON.stringify(path, 0, 4) + '</pre>');