用递归遍历树很奇怪（JavaScript）

Question

我已经开始深入研究树的主题。而且我发现了奇怪的（对我来说）行为。

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
    else return 0
  }
}

所以，我在这里创建了一个节点结构，它得到一个整数数组，并将其分成两半，直到叶子不只包含数组的一个元素。

let n_array = [1,3,2,5];
root_node = new tree_node(n_array);

现在我想遍历树并提醒每个节点的“n_array”。我本来以为应该是这样的

function show_tree(root_node){
  if (root_node.descendants.lenght != 0){
    root_node.descendants.forEach(element => {
      return show_tree(element);
    });
  }
  else {
    alert(root_node.n_array)
    return 0;
  } 
}

但是没用。如果我使用网络浏览器控制台，那么 root.descendants.length 会给出长度。但在我的递归中，它没有。每次都是undefined

我从代码中删除了越来越多的内容，最后，我得到了这个。

function show_tree(root_node){
  alert(root_node.n_array)
  root_node.descendants.forEach(element => {
    return show_tree(element);
  });  
}

工作解决方案有效，但我不明白为什么。我预计它会运行出错，因为在树的末尾 root_node.descendants 将是 未定义.

更糟糕的是 - 我不明白为什么在每次调用 root_node.descendants !=0[ 时递归都会停止并且不会进入无限循环=44=] ... 请帮助我理解

为什么我的第一个版本 show_tree 不起作用

为什么最后一个有效。

Answer 1

您已经有效地构建了一个看起来像这样的树结构：

    [1, 3, 2, 5]
      /       \
  [1, 3]     [2, 5]
   /   \      /   \
  [1]  [3]   [2]   [5] 
   |    |     |     |
  [ ]  [ ]   [ ]   [ ]

在您的第一个函数中，您遇到了一些问题。直接的问题是您使用的是 .lenght 而不是 .length。关于您的函数，接下来要注意的是它何时执行 alert()s。在您的情况下，您仅在节点具有空数组作为其 descendants 属性时才执行 alert()。在上面的树图中，您会注意到只有最后一个节点 [1]、[3]、[2] 和 [5] 是这种情况，因此这些节点会收到警报。您遍历的所有其他节点都有非空后代，因此屏幕上不会 alerted/logged:

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
  }
}

let n_array = [1,3,2,5];
root_node = new tree_node(n_array); 

function show_tree(root_node){
  if (root_node.descendants.length != 0){
    root_node.descendants.forEach(element => {
      show_tree(element);
    });
  }
  else {
    console.log(root_node.n_array); // replaced with console.log (as this is a more preferred way of logging data)
  } 
}

show_tree(root_node);
// Logs:
// [1]
// [3]
// [2]
// [5]

与您的第一个函数不同，您的第二个函数会提醒它访问的每个节点，而不仅仅是那些没有后代的节点。那是因为你的 alert() 是函数的第一行，所以它总是运行调用 show_tree() 函数的每个节点的警报。

I expect that it will run into an error, because at the end of the tree root_node.descendants will be undefined

如果您查看 tree_node class，您会注意到您创建的每个节点都有一个 descendants 属性并分配给一个空数组在你的构造函数中。因此，当您 traverse/loop 在您的树上进行进一步的递归调用时，您传递给 show_tree() 函数的每个节点都会有一个 descendants 属性 - 有时 descendants 的一个节点将是一个空数组。因此，当您使用时不会发生错误：

root_node.descendants.forEach(..)

因为在空数组 ([]) 上调用 .forEach() 是有效的。这就引出了你的另一个问题……:

I don't understand why this recursion stops and does not go into an endless loop

当您遍历树中的节点时，您最终会到达 叶节点 （没有后代的节点（.descendants 是一个空数组））。发生这种情况时，您的 .forEach() 循环将不会运行其“回调”中的代码，因此不会对 show_tree() 进行进一步的递归调用。相反，函数 returns 到它的调用者，它可以开始“解开”递归调用或继续循环遍历其他兄弟节点。

Answer 2

我相信您问题的答案是：

root_node.descendants.lenght != 0行有错字，我们可以改成root_node.descendants.length != 0
root_node.descendants 不会是 undefined，它会是 []，或者一个空数组，所以 forEach 根本不会运行，这可能是期望的行为。

我稍微修改了您的方法，包括 v1 和 v2 后缀以区分它们，并添加了 depth 参数，因此我们可以记录节点深度。此外，我们不使用 alert()，而是使用 console.log().

运行我认为每个现在都有效，v1 方法将仅记录叶节点，而 v2 方法将记录所有节点。

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
    else return 0
  }
}

function show_tree_v1(root_node, depth = 0) {
  if (root_node.descendants.length != 0){
    root_node.descendants.forEach(element => {
      return show_tree_v1(element, depth + 1);
    });
  } else {
    console.log('show_tree_v1: [', root_node.n_array.join(","), '] , depth:', depth)
    return 0;
  } 
}

function show_tree_v2(root_node, depth = 0){
  console.log('show_tree_v2: n_array: [', root_node.n_array.join(","), '], depth:', depth)
  root_node.descendants.forEach(element => {
    return show_tree_v2(element, depth + 1);
  });  
}

let n_array = [1,3,2,5];
root_node = new tree_node(n_array);

console.log('Show tree (v1):')
show_tree_v1(root_node)

console.log('Show tree (v2):')
show_tree_v2(root_node)

.as-console-wrapper { max-height: 100% !important; top: 0; }

用递归遍历树很奇怪（JavaScript）

Traversing tree with recursion works strange (JavaScript)

javascript

tree

recursion