使用 Javascript 的 BST 递归添加方法不起作用

Question

下面是一个带有插入函数的BST的实现。目前，该代码不起作用；它只会吐出 Tree { root: null }

当我尝试调试它时，它似乎成功地将新节点添加到正确的位置，但是一旦它从函数中 returns，所有数据都丢失了，它最终没有插入任何东西.

代码如下：

class Node {
    constructor(value) {
        this.value = value
        this.left = null;
        this.right = null;
    }
}

class Tree {
    constructor() {
        this.root = null
    }

    insert(value) {
        const insertHelper = (value, node) => {
            if (node === null) {
                node = new Node(value)
                return null
            } else if (node.value === node.value) {
                console.log("Value exists.")
                return null;
            } else if (node.value < node.value) {
                return this.insertHelper(node, node.right)
            } else {
                return this.insertHelper(node, node.left)
            }
        }

        return insertHelper(value, this.root)
    }

}

var tree = new Tree;
tree.insert(10)
tree.insert(5)

console.log(tree);

Answer 1

几个问题：

this.root 永远不会被修改。函数参数按值传递，因此如果您将 this.root 作为参数传递，并且函数将新值分配给相应的参数变量 node，这将 而不是 影响 this.root。解决方案是让辅助函数 return 作为参数传递的节点的新值，这样您就可以将它分配回根（或其他节点）。
您在多个地方将 node.value 与 node.value 进行了比较。那是一个错误。比较应该涉及 value.
递归调用将 node 作为第一个参数传递，而函数期望将值作为第一个参数。

这是更正后的代码：

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class Tree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const insertHelper = (value, node) => {
            if (node === null) {
                node = new Node(value);
            } else if (node.value === value) {
                console.log("Value exists.");
            } else if (node.value < value) {
                node.right = insertHelper(value, node.right);
            } else {
                node.left = insertHelper(value, node.left);
            }
            return node;
        }
        this.root = insertHelper(value, this.root);
    }
}

var tree = new Tree;
tree.insert(10);
tree.insert(5);
console.log(tree);

注意：明确使用 semi-colons。靠了automatic semi-colon insertion is asking for trouble。总有一天它会打击你。

使用 Javascript 的 BST 递归添加方法不起作用

Recursive Add method for BST using Javascript not working

javascript

recursion

binary-search-tree