不确定这是广度优先还是深度优先搜索？

Question

我正在复习 bfs 和 dfs 概念，最近为 Trie 树编写了这个搜索方法。我相信它是 bfs 因为如果下一个值存在，我们会从根开始搜索每个级别。我不确定在这样的问题中实施 dfs 会是什么样子。不过我可能完全错了。

class TrieTree {
  constructor() {
    this.root = new TreeNode();
  }
  insert(word) {
    let currentNode = this.root;
    for (let char of word) {
      if (currentNode.children.has(char)) {
        currentNode = currentNode.children.get(char);
        continue;
      } else {
        currentNode.children.set(char, new TreeNode(char));
        currentNode = currentNode.children.get(char);
      }
    }
    currentNode.isWord = true;
  }
  //I'm not sure if this should be called bfs or dfs
  bfs(searchTerm) {
    let currentNode = this.root;
    for (let char of searchTerm) {
      if (currentNode.children.has(char)) {
        currentNode = currentNode.children.get(char);
      } else {
        return false;
      }
    }
    return (currentNode.isWord)
  }
}

class TreeNode {
  constructor(val) {
    this.data = val;
    this.children = new Map(); //collection of nodes in TS we would use TreeNode[];
    this.isWord = false;
  }
}

let tree = new TrieTree();

tree.insert("hello");
tree.insert("bucky");
tree.insert("hell");

console.log(tree.bfs("bucky"));

Answer 1

两者都不是。您不是在迭代整棵树，这可以通过 bfs 或 dfs 方式完成。您只是在 trie 中访问您期望的位置的元素。此查询操作通常称为 find、get 或 has.

Answer 2

给定

tree.insert("helios");
tree.insert("hello");
tree.insert("helipad");

您的数据结构如下所示：

    h
    |
    e
    |
    l
   / \
  i   l
 / \   \
o   p   o
|   |
s   a
    |
    d

但是，由于每个级别都是作为地图实现的，并且搜索使用 Map#has/Map#get，因此无法搜索整个 space。在查找"helipad"时，算法不会考虑h -> e -> l之后的第一个分支，它会直接跳转到i部分并丢弃l分支.同样，在 h -> e -> l -> i 之后，它不会将 o 视为可能的路径，而是直接继续 p。这不是广度优先搜索的工作原理。

这也不是深度优先搜索的工作方式，因为如果是深度优先搜索，它会首先尝试 h -> e -> l -> i -> o -> s，然后回溯到 i 并尝试 h -> e -> l -> i -> p -> a -> d。

不确定这是广度优先还是深度优先搜索？

Unsure if this is breadth first or depth first search?

javascript

tree

depth-first-search

breadth-first-search