C++从当节点有两个孩子

假设我有一棵树如下树删除节点：C++从当节点有两个孩子

如果我想删除3，用最低的左节点替换它（在这种情况下， 1）。 2将附加到4，在该图中。

我该如何编码？

我知道你必须继续遍历一些循环，然后重新设置每个指针。此外，您必须考虑最后一个左节点可能有正确子节点的情况。

来源

2012-06-07 forthewinwin

您尝试过什么？你应该明白，我们不是在这里做你的功课：http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions – chembrad

你不*要*下降到最左边的节点。您需要左子树的最右端节点或右子树的最左端节点。由于'1'和'2'都下降到'4'的* left *，所以你可以提升'4'来代替'3'，而不是'1'（如果你把'1'移到上面，那么搜索树将不再有效（它的左后代会比它更大，违反了树的基本规则） –

@JerryCoffin：树已经失序，当我读它时，遍历是1 2 4 3 5 8 6 12 15 – jxh

我们解决之前， “怎么做”，两件事情：

（1） - 这是次要的。这个问题仅在二进制搜索树（BST）的背景下才有意义，而不仅仅是一个二叉树。而且这棵树不是BST，因为3和4是交换的。（2） - 任何时候你在BST上执行删除操作，并且你想“修复”树使得生成的树也是BST，你有两种选择：（a）你可以选择（b）您可以选择要删除的节点的右侧子树中的最小值，然后将其与要删除的节点进行交换。（你应该说服自己，为什么这些选项都会让你成为BST）。在你的例子中（正确放置3和4），这意味着将4与3或5交换。

现在为“如何”做到这一点。假设我们从上面选择了选项（a）。你需要做的是编写一个函数，从4开始，将会走一步，然后尽可能长地遍历（你也应该说服自己为什么这是正确的）。一旦你不能再遍历到右边，你知道你已经在左子树中找到了最大的值。然后，将该值替换为要删除的节点，然后删除刚刚取得的节点值。

如果你已经想出了如何对你在这里展示的树进行编码，这实际上很简单。如果您有特定代码问题，请提供更多详细信息

来源

2012-08-21 23:52:22

C++从当节点有两个孩子

回答

相关问题