JavaScript 递归函数参数

#1 在进行递归调用的过程中发生变化，从而改变它返回的内容;#2 没有。调试器将有助于明确这如何导致节点“丢失”。node

也许这会有所帮助。以下内容可能看起来不正确：

insert(value, node = this.tree) {
    if (node == null) return node = new Node(value)
    if (value == node.key) return node; // prevent dublicated values;
    if (value > node.key) {
        node = node.right;
        node.right = this.insert(value, node);
    } else if (value < node.key) {
        node = node.left;
        node.left = this.insert(value, node);
    }
    return node;
}

当然不是。我们不想在返回之前更改其标识。但从本质上讲，这就是你的代码的作用。 此行的作用与上面的块相同：nodeif

if (value > node.key) node.right = this.insert(value, node = node.right);

首先，我们将变量的值重新赋值为 。然后我们调用 with new node 值。然后在函数的末尾，我们返回 ，并返回其新值。nodenode.rightinsertnode

有一个强有力的论据，永远不要重新分配输入参数。这只是这个想法的一个证据。

无法访问的代码

为了配合 Scott Sauyet 的回答，我建议你也简化你的条件。if..

insert(value, node = this.tree) {
  if (node == null)          // ..
  if (value == node.key)     // ..
  if (value > node.key)      // ..
  else if (value < node.key) // ..
  return node                // ???
}

想想看——如果值不小、不大、不等，那它是什么？撇开错误不谈（来自不正确的值），它是冗余的、无法访问的代码。如果该值既不大也不小，则它必须相等 -???

insert(value, node = this.tree) {
  if (node == null)      // node is empty
  if (value > node.key)  // value is greater (implicit: node not empty)
  if (value < node.key)  // value is lesser  (implicit: node not empty; value not greater)
  return node            // value is equal   (implicit: node not empty; value not greater, not lesser)
}

持久性数据结构

重新分配（或任何突变）也使我们的计划更难考虑。我们可以创建新节点，而不是改变旧节点。当一个数据结构保证它永远不会改变时，它被称为持久性数据结构——

insert(value, node = this.tree) {
  // is the node empty?
  if (node == null)
    return new Node(value)

  // the node is not empty. is the value greater?
  else if (value > node.key)
    return new Node(node.value, node.left, this.insert(value, node.right))

  // the node is not empty and the value is not greater. is it less?
  else if (value < node.key)
    return new Node(node.value, this.insert(value, node.left), node.right)

  // the node is not empty and the value is neither greater nor lesser
  else
    return node
}

面向模块的设计

最后，我建议将树函数与类解耦 -

// tree.js
const empty = Symbol("tree.empty")

const node = (value, left = empty, right = empty) =>
  ({ value, left, right })
  
const insert = (t, value) => {
  if (t === empty)
    return node(value)
  else if (value < t.value)
    return node(t.value, insert(t.left, value), t.right)
  else if (value > t.value)
    return node(t.value, t.left, insert(t.right, value))
  else
    return t
}

const fromArray = (arr) => arr.reduce(insert, empty)

const toString = (t) => ...

那么如果你想要一个面向对象的接口，就把它创建成一个围绕普通函数接口的薄包装器——

// tree.js (continued)
class tree {
  static fromArray(arr) { return new tree(fromArray(arr)) }
  constructor(t) { this.t = t }
  insert(value) { return new tree(insert(this.t, value)) }
  toString() { return toString(this.t) }
}

通过模块导出两个接口 -

// tree.js (continued)
export { empty, fromArray, insert, node, toString }
export default tree

现在，您的模块提供了双接口。您可以使用功能模块并利用摇树 -

import { insert, fromArray, toString } from "./tree.js"

const mytree = insert(
  fromArray([3, 2, 4, 1, 6, 7, 5, 8, 10, 9, 12, 11]),
  100
)

console.log(toString(mytree))

或者你可以通过类接口导入整个模块——

import tree from "./tree.js"

const mytree = tree
  .fromArray([3, 2, 4, 1, 6, 7, 5, 8, 10, 9, 12, 11])
  .insert(100)

console.log(mytree)