仅具有1个节点（根节点）的二叉搜索树上的删除操作

Question

开始为不平衡的BST结构编写删除函数。为第一种情况手动运行一些测试（节点没有子节点）。决定在大小为1的树上运行它（仅在根上），出于某种原因，它似乎没有按照我在本语句第3行期望的方式将根重新分配到null：

return direction ?
  parent[direction] :
  node = null;

然后，当我在单节点树上运行inOrderTraversal时，它应该只是控制台。记录每个节点，并为空树返回undefined（我所期望的），它只是像删除之前一样打印55。

它似乎适用于要删除的节点没有子节点的所有其他情况。

这是小提琴：https://jsfiddle.net/uvdrmwh0/6/

和代码：

"use strict";

function Node(value, left = null, right = null) {
  return {
    value,
    left,
    right
  };
}

function insert(x, root) {
  let currNode = root;
  while (currNode) {
    if (x < currNode.value) {
      if (currNode.left) {
        currNode = currNode.left;
      } else {
        currNode.left = Node(x);
        return;
      }
    } else if (x > currNode.value) {
      if (currNode.right) {
        currNode = currNode.right;
      } else {
        currNode.right = Node(x);
        return;
      }
    } else if (x === currNode.value) {
      throw new Error("cannot insert node with the same value as an existing node");
    } else {
      throw new Error("undefined behavior in insert");
    }
  }
  throw new Error("failed to insert");
}

function remove(x, node, parent = null, direction = null) {
  if (node === null) return;
  if (node.value === x) {
    if (!node.left && !node.right) {
      return direction ?
        parent[direction] = null :
        node = null;
    } else if (node.left && !node.right) {
        //TODO
    }
    //TODO
  }
  direction = x < node.value ? "left" : "right";
  remove(x, node[direction], node, direction);
}

function inOrderTraversal(node) {
  if (node === null) return;
  inOrderTraversal(node.left);
  console.log(node.value);
  inOrderTraversal(node.right);
}

function BinarySearchTree(seed) {
  if (!Array.isArray(seed)) {
    throw new Error("BinarySearchTree must be seeded with an array");
  }
  let root = Node(seed[0]);
  seed.slice(1).forEach(x => {
    insert(x, root);
  });
  return root;
}

let bst = BinarySearchTree([55]);
inOrderTraversal(bst);
console.log("---------after removal---------");
remove(55, bst);
inOrderTraversal(bst);

我注意到像这样的工作：

let x = { a: 1 };
function changeProperty(obj, key, newValue) {
  obj[key] = newValue;
}
changeProperty(x, "a", "hello");
console.log(x.a); //prints hello

但这并没有：

function reassignObject(obj) {
    obj = { a: "some new value" };
}
reassignObject(x);
console.log(x.a); //still prints hello

似乎您可以重新分配对象的属性（对象中的指针），它将更改外部引用，但将引用重新分配到对象本身却不会？




Answer 1

以下更改将使其正常工作：

console.log("---------after removal---------");
bst = remove(55, bst); //change here

对节点的更改在remove函数中本地发生。因此，您应该将bst设置为从remove函数返回的内容。

这里需要了解的重要一点是javascript如何传递参数。我希望这有帮助。