javascript - 在嵌套树中定位元素 - JavaScript

Question

需要帮助编写一个函数来搜索示例树中的元素。

var sampletree = [
  "a",
  "b",
  "c",
  [
    "d",
    "e",
    [
      "f",
      "h",
      "i",
      [
        "z",
        "x"
      ]
    ]
  ],
  [
    "y",
    "q",
    "t",
    [
      "m",
      "n",
      [
        "o",
        "p"
      ],
      [
        "r",
        "s",
        [
          "u",
          "v"
        ]
      ]
    ]
  ],
  "g"
]

想要通过仅使用 javascript 的广度优先搜索搜索树中的内部元素(例如 o、p、u、v)来返回 true/false。

我使用了for循环来运行然后.indexOf，但无法获取它。

Answer 1

您可以使用此功能:

function findNodeBFS(tree, node) {
    var queue = tree.slice();
    for (var i = 0; i < queue.length; i++) {
        if (queue[i] === node) return true;
        if (Array.isArray(queue[i])) queue = queue.concat(queue[i]);
    }
    return false;
}

var sampletree = [ "a", "b", "c", [ "d", "e", [ "f", "h", "i", [ "z", "x" ] ] ], [ "y", "q", "t", [ "m", "n", [ "o", "p" ], [ "r", "s", [ "u", "v" ] ] ] ], "g" ];

console.log(findNodeBFS(sampletree, "u")); // true
console.log(findNodeBFS(sampletree, "j")); // false

说明

该算法维护一个 queue ，您可以将其视为一种“待办事项”列表。它从树的副本开始。该代码迭代节点，但仅限于顶层节点。每当它遇到一个数组(代表更深层次)时，这些子元素就会被添加到队列的末尾，这意味着:“我稍后会处理你”。

这就是这行代码中发生的情况:

if (Array.isArray(queue[i])) queue = queue.concat(queue[i]);

因此，如果 queue[i] 是一个数组，则其元素将附加¹(浅复制)到队列中。

_{¹ 事实上，concat不会改变给定的数组，而是产生一个新的数组，它是 queue 和 queue[i] 的串联。通过将新数组分配回队列，我们得到了追加的效果。相反，我们可以这样做 [].push.apply(queue,queue[i])，它通过就地附加第二个来改变第一个。但它可能看起来有点神秘。}

请注意，我们不会追加找到的数组，而是追加其中的数组中的每个元素。因此，当循环到达附加数据时，它实际上会访问原始树的更深层次。这确实是BFS的意思:首先访问当前所在关卡的节点，完成当前关卡后才处理更深的关卡。队列(先进先出)是实现此目的的理想数据结构。

深度优先搜索变体

DFS 变体将是这个递归 ES6 函数:

function findNodeDFS(tree, node) {
    return Array.isArray(tree) && tree.some( val => findNode(val, node) ) 
           || node === tree;
}