删除二叉搜索树中的节点
Remove the node in Binary Search Tree
如何用一种方法删除二进制搜索树中的所有 isRemoved=true; 数据？
或者两个没关系。
已经有一个删除方法，它标记了来自方法 isRemoved=true 的节点。
因此，构造函数有四个特化，它们是 Type data、left、right、isRemoved。
该方法是否可以递归工作无关紧要。
我的想法是，当我找到删除的go和delete方法并删除它时，遍历所有节点然后返回并继续查看节点。我无法实现这个想法，因为 BST 很复杂。你们能给我一些线索吗？
首先，您需要决定如何遍历树（中序、前序、后序）。
然后你将处理三个不同的情况来删除一个节点；当节点是叶子时，当节点有一个时child，当节点有左右时child.
- 如果节点是叶节点，您可以将其删除。
- 如果节点有child，可以设置节点的child为parent节点的child，然后删除节点
- 如果节点有两个children，可以到左边child的子树，用左子树最右边的child替换节点。由于子树中最右边的节点是叶子节点，您可以在不重新平衡树的情况下进行替换。
使用上述方法之一在删除 isRemoved=true 节点的同时遍历树，直到到达遍历中的最后一个节点。
如何用一种方法删除二进制搜索树中的所有 isRemoved=true; 数据？
或者两个没关系。
已经有一个删除方法，它标记了来自方法 isRemoved=true 的节点。
因此，构造函数有四个特化，它们是 Type data、left、right、isRemoved。
该方法是否可以递归工作无关紧要。
我的想法是，当我找到删除的go和delete方法并删除它时，遍历所有节点然后返回并继续查看节点。我无法实现这个想法，因为 BST 很复杂。你们能给我一些线索吗？
首先，您需要决定如何遍历树（中序、前序、后序）。
然后你将处理三个不同的情况来删除一个节点；当节点是叶子时，当节点有一个时child，当节点有左右时child.
- 如果节点是叶节点，您可以将其删除。
- 如果节点有child，可以设置节点的child为parent节点的child，然后删除节点
- 如果节点有两个children，可以到左边child的子树，用左子树最右边的child替换节点。由于子树中最右边的节点是叶子节点，您可以在不重新平衡树的情况下进行替换。
使用上述方法之一在删除 isRemoved=true 节点的同时遍历树，直到到达遍历中的最后一个节点。