递归JSON数据结构的遍历算法

Question

我正在用Javascript构建一个图形编辑器，我需要一个算法来识别两个“节点”对象之间所有可能的路由。

给定以下JSON对象：

{
    "failureNode": {
        "failureNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",}
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-2",
        },
        "successNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-3",
        },
        "id": "node-4",
    },
    "successNode": {
        "failureNode": null,
        "successNode": null,
        "id": "node-endpointsuccess",
    },
    "id": "node-root",
}

我需要ID为'node root'的节点之间的所有可能路由

1. 开始-

对于这个例子，输出将是一个JSON路径数组。像这样的东西...

[
    failureNode.failureNode.failureNode.failureNode,
    failureNode.successNode.failureNode.failureNode
]

大多数应用程序都使用jQuery，所以纯Javascript或jQuery解决方案都可以工作。

Answer 1

我觉得你选择的表达方式有点奇怪和混乱。树不是表示这一点的最佳方式。您所描述的本质上是一个DAG（有向无环图）。递归表示最终会复制对象。虽然我确信还有其他方法来表示这一点，但一个简单的表示方法就是列出每个节点，其中包含由id标识的成功和失败节点。停止节点的成功和失败节点将具有空值（或零长度字符串，以两者中的任何一个为准）。或者你可以有一本关于所有这些的字典。

例如，您的图形可以（按列表）描述为：

[
  {
    id: "Start",
    successNode: "success",
    failureNode: "node-1"
  },
  {
    id: "node-1",
    successNode: "node-3",
    failureNode: "node-2"
  },
  {
    id: "node-2",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-3",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-4",
    successNode: "success",
    failureNode: "failure"
  },
  {
    id: "success",
    successNode: "",
    failureNode: ""
  },
  {
    id: "failure",
    successNode: "",
    failureNode: ""
  }
]

使编辑图表变得非常容易。只需添加或删除节点及其值。我可能会使用另一个对象作为字典，以便更快/更容易地找到每个节点。假设我确实有这样一个字典dicing，从一个节点导航到另一个节点查看您最终的位置并不难。

Answer 2

这将完成以下任务：

function recurse(from, to, node) {
    var result = [],
        choices = ["sucessNode", "failureNode"];
    if (!from && to == node.id)
        return [[]];
    if (from == node.id)
        return recurse(null, to, node);
    for (var i=0; i<choices.length; i++) {
        var choice = choices[i];
        if (node[choice] != null) {
            var res = recurse(from, to, node[choice]);
            for (var j=0; j<res.length; j++) {
                res[j].unshift(choice);
                result.push(res[j]);
            }
        }
    }
    return result;
}
recurse('node-root', 'node-endpointfailure', data);