algorithm - 有没有办法在没有根节点引用的情况下删除二叉树中的任何节点？

Question

我正在尝试解决这个问题，但无法破解。我们有一个二叉树，我想从树中删除给定的节点，但我们没有根节点的引用。我想知道如何在没有根节点引用的情况下执行此操作。我们确实有对 node5 的引用，如图中所示。

Answer 1

更新考虑到新的编辑。

因为这不是二叉搜索树，在这种情况下，我假设树中的节点顺序不相关并且该树不会有重复项，因此可以使用我们上面定义的相同数据结构删除 node5，但我们需要包含一个 parent node 引用(对于 第 3 步详见下文):

node {
   d: data
   leftChild: node
   rightChild: node
   parent: node
}

现在我们可以移除 node5 修改树，而无需访问/修改 root (node1)。

您必须执行以下操作:

(Remember that node 5 is also a Binary subtree, so after modifying it, we want the whole Binary Tree to still remain one!)

1. 找到 node5 的最深 节点。您需要将 node5 的节点引用作为树进行遍历。

(*Be careful with how you pass the arguments. root should be a copy, so that it doesn't mess with node5' as a root, but level and deepestNode should be references.)

findDeepestNode(root: node, level: integer, deepestNode: node) {
    if (root != null) {
         level = level + 1
         find(root.left, level)
         if (level > deepestlevel) {
            deepestNode = root;    // node reference to the deepestNode
            deepestlevel = level;
      }
      find(root.right, level);
   }
}  

---

执行此操作后，deepestNode 在您的情况下将是 node7 或 node8。没关系。

---

1. 现在使node5 的值等于deepestNode 的值。在我们的伪代码中:

node5.data = deepestNode.data // Replacing node5's value with the deletingNode's one.

1. 树现在有一个重复值。你还有 deepestNode。所以现在您将 deepestNode parent's reference 分配给 null 并删除deepestNode 作为引用。 这一步是我们需要包含父节点引用的原因。

您的删除已完成!