javascript - 为 Javascript 二进制搜索树编写递归添加方法

Question

我正在尝试在 JS 中为 BST 编写一个添加/插入方法，但由于某种原因似乎无法让它工作。我的代码在这里:

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


function BinarySearchTree() {
    this.root = null;

    this.add = function(insertElem){
        let currNode = this.root;

        var recurInsert = function(elem, node){
            if(node == null){
                let newNode = new Node(elem);
                node = newNode;
                console.log("firstNode");
                return undefined;
            }
            else if(elem == node.value){
                console.log("equal val");
                return null
            }
            else if(elem > node.value){
                console.log("go right");
                recurInsert(elem, node.right);
            }
            else{
                console.log("go left");
                recurInsert(elem, node.left);
            }
        }

        recurInsert(insertElem, currNode);
    }
}

具体来说，node = newNode 行实际上并未将 node 设置为 newNode。我怀疑这可能与 JavaScript 的按值传递性质有关，但我不完全确定。

我哪里出错了？

此外，如果可能的话，我希望暂时保留这种递归形式。

Answer 1

基本上您需要将对象引用交给递归函数，因为如果没有，您将创建新节点而不链接到根节点。

此代码将一个对象和方向作为键，并检查要做出的四个不同的决定。如果必须分配新节点，则使用对象和 key 。

如果一个值小于或大于节点的值，则使用该节点以及新的方向进行检查。

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

function BinarySearchTree() {
    this.root = null;
    this.add = function (value) {

        function check(node, direction) {
            if (node[direction] === null) {
                node[direction] = new Node(value);
                console.log('new node', value);
                return;
            }
            if (node[direction].value === value) {
                console.log('equal value', value);
                return;
            }
            if (node[direction].value > value) {
                console.log('go left', node[direction].value);
                check(node[direction], 'left');
                return;
            }
            if (node[direction].value < value) {
                console.log('go right', node[direction].value);
                check(node[direction], 'right');
            }
        }

        check(this, 'root');
    };
}

var tree = new BinarySearchTree;

tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);

console.log(tree);

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

使用默认节点的更短方法。

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

function BinarySearchTree() {
    this.root = null;
    this.add = function (value) {

        function check(node) {
            if (node.value === value) {
                return;
            }
            if (node.value > value) {
                check(node.left = node.left || new Node(value));
                return;
            }
            if (node.value < value) {
                check(node.right = node.right || new Node(value));
            }
        }

        check(this.root = this.root || new Node(value));
    };
}

var tree = new BinarySearchTree;

tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);

console.log(tree);

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

改变对象与属性的小例子

function assign(o) {      // take object reference as value of o
    o = { bar: 43 };      // assign a new value to o, object keeps it value
    console.log('o', o);  // the reference to object is replaced by an own object
}

function change(o) {      // take object reference as value of o
    o.bar = 41;           // take object reference and assign a new property
    console.log('o', o);  // because of the object reference, o and object has changed
}

var object = { foo: 42 };
console.log('object', object);

assign(object);
console.log('object', object);

change(object);
console.log('object', object);

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