如何删除所有 isRemoved=true; 数据在二叉搜索树中的一种方法？一两个都没关系。已经有一个remove方法，它标记来自该方法的节点 isRemoved=true . 所以，构造器有四个特殊化，它们是 Type data , left , right , isRemoved . 方法是否可以递归工作并不重要。
我的想法是遍历所有的节点，当我找到删除的go和delete方法并删除它，然后返回并继续查看节点。我无法实现这个想法，因为bst很复杂。你们能给我一些线索吗？
1条答案
按热度按时间ac1kyiln1#
首先，您需要决定如何遍历树（按顺序、按前顺序、按后顺序）。
然后，您将为要删除的节点处理三种不同的情况；当节点是叶子时，当节点有一个子节点时，当同时有一个左子节点和一个右子节点时。
如果节点是叶子，则可以将其移除。
如果节点有子节点，则可以将节点的子节点设置为父节点的子节点，然后移除该节点。
如果节点有两个子节点，则可以转到左子树的子树，并用左子树最右边的子节点替换该节点。由于子树中最右边的节点是叶子，因此可以替换而不必重新平衡树。
遍历树，同时使用上述方法之一删除isremoved=true节点，直到到达遍历中的最后一个节点。