javascript - 删除只有 1 个节点(根)的二叉搜索树的操作

Question

开始为不平衡的 BST 结构编写删除函数。为第一种情况手动运行一些测试(节点没有子节点)。决定在大小为 1 的树(只是根)上运行它，并且出于某种原因，它似乎没有像我期望的那样将根重新分配给 null 的第 3 行这个声明:

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

然后，当我在单节点树上运行 inOrderTraversal 时，它应该只是 console.log 每个节点，并为空树返回 undefined(我所期待的) 它只是像删除之前一样打印 55。

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

这是 fiddle :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

node 的更改发生在本地 remove 函数中。因此，您应该将 bst 设置为从 remove 函数返回的任何值。

这里要理解的重要一点是how does javascript pass the arguments .我希望这会有所帮助。