树数据结构中的 DFS - 此递归函数中的基本情况是什么？

Question

（我不是母语人士。我为我糟糕的英语道歉）

如果有一棵像下面这样的树。

每个节点都是一个对象。

ex) nodeA.data = 23, nodeA.children = [nodeB, nodeC]

如果我们在 DFS 中从根开始搜索这棵树，结果将是

23 - 19 - 15 - 22 - 35 - 31 - 38

下面的代码是 DFS 的一个实现，它成功地记录了与上面相同的结果。

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
  
  // ... omit  

  depthFirstTraversal() {
    console.log(this.data);
    this.children.forEach(child => child.depthFirstTraversal());
  }
}

但我很好奇:

如果在forEach循环中重复递归调用，最后“child”参数指向nodeD怎么办？

Answer 1

你担心的情况不会发生。

如果在 children 数组中有 undefined 值，forEach 回调中的 child 变量只能是 undefined。但那将是一件奇怪的事情。实际上，当 this 是叶节点（如节点 D）时，它将有一个 empty this.children 数组，因此 forEach 循环不会进行任何迭代，也不会调用其回调函数。

这就是实现递归的基本情况：当this.children.length == 0.

树数据结构中的 DFS - 此递归函数中的基本情况是什么？

DFS in Tree data structure - What is the base case here in this recursive function?

tree

recursion

depth-first-search

data-structures