删除BST节点有两个孩子时

我想删除BST中有两个子节点的节点。例如，删除BST节点有两个孩子时

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

2012-12-05 mumair

这是功课？你有什么尝试？ – atoMerz

所以哪一个呢？ Java，C或C++？ –

将数据从包含6的节点移动到包含12的节点，用12覆盖12。删除包含6的叶节点。 –

您需要获取其左子树的最右侧子元素，或者右子树的最左侧子元素（例如6或15），并将其中一个移动到该位置，那么你可以删除你想要的节点。

如果您正在做任何事情来跟踪子树中的节点数量，您通常希望从较大的子树中选取节点，因此当您移动它时，树会至少平衡，因为它开始。例如，在这种情况下，获得6比15来保持平衡更好 - 但是如果你只是有一个普通的，不平衡的BST，那么你可能没有那种容易获得的信息。

2012-12-05 05:22:41

有这样的算法第4版的图书网站商量好了：http://algs4.cs.princeton.edu/32bst/

2012-12-05 05:27:59 udeleng

回答