在嵌套树中定位元素 - 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"
]

想要 return true/false 通过只使用广度优先搜索 javascript 在树中搜索 o、p、u、v 等内部元素而不使用框架/库.

我使用 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，您可以将其视为一种 "to do" 列表。它以树的副本开始。代码遍历节点，但仅遍历 top-level 处的节点。每当它遇到一个代表更深层次的数组时，那些 children 被添加到 queue 的末尾，意思是："I will deal with you later".

这就是这行代码中发生的事情：

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

所以如果queue[i]是一个数组，它的元素被附加¹（浅拷贝）到队列中。

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

请注意，我们没有追加我们找到的 array，而是 in 中的每个元素。所以当循环到达附加数据时，它实际上会访问原始树的更深层次。这确实是 BFS 的意思：首先访问你当前所在层级的节点，当你完成当前层级后才处理更深的层级。队列（先进先出）是执行此操作的理想数据结构。

深度优先搜索变体

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

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

在嵌套树中定位元素 - JavaScript

Locating element in a nested tree - JavaScript

javascript

tree

search

dom

breadth-first-search

说明

深度优先搜索变体