0

我正在尝试删除 BST 中具有两个子节点的节点。例如，

     |
    12
   /  \
  5    15
 / \     \
2   6    20

我想删除包含 info=12 的节点。我需要帮助来执行此操作。

4

2 回答 2

5

您需要获取其左子树的最右边的孩子，或者其右子树的最左边的孩子（在您的示例中为 6 或 15），并将其中一个移动到该位置，然后您可以删除你想要的节点。

如果您正在做任何事情来跟踪子树中的节点数，您通常希望从较大的子树中选择节点，因此当您移动它时，树将至少与它开始时一样平衡. 例如，在这种情况下，获得 6 比 15 更好，以帮助保持平衡——但如果您只有一个普通的、不平衡的 BST，您可能无法轻松获得该信息。

于 2012-12-05T05:22:41.720 回答
0

在算法第 4 版的书籍网站上有一个很好的讨论：http: //algs4.cs.princeton.edu/32bst/

于 2012-12-05T05:27:59.187 回答