1

我正在尝试编写代码来删除BST的所有节点（每个节点只有三个属性，左，右和数据，没有父指针）。下面的代码是我想出的，它只删除树的右半部分，保持左半部分不变。如何修改它以便也删除左半部分（这样最终我只剩下既没有左子树也没有右子树的根节点）？

def delete(root):
    global last
    if root:
     delete(root.left)
     delete(root.right)
     if not (root.left or root.right):
        last = root
     elif root.left == last:
        root.left = None
     else:
        root.right = None

其次，任何人都可以建议使用堆栈或其他相关数据结构的迭代方法吗？

4

4 回答 4

4

如果要删除两个子树，则无需递归。只需设置root.left并root.right让None垃圾收集器处理它们。实际上，与其一开始delete就创建一个函数，不如直接设置root = None并完成它！

编辑：如果您需要对数据值运行清理代码，如果 GC 做得不够，您可能希望通过树递归来获取所有这些值。拆除树中的链接实际上并不是必需的，但我也会这样做：

def delete(node):
    if node:
        node.data.cleanup() # run data value cleanup code

        delete(node.left)   # recurse
        delete(node.right)

        node.data = None    # clear pointers (not really necessary)
        node.left = None
        none.right = None

您还询问了遍历树的迭代方法，这有点复杂。这是一种使用deque（作为堆栈）来跟踪祖先的遍历方法：

from collections import deque

def delete_iterative(node):
    stack = deque()
    last = None

    # start up by pushing nodes to the stack until reaching leftmost node
    while node:
        stack.append(node)
        node = node.left

    # the main loop
    while stack:
        node = stack.pop()

        # should we expand the right subtree?
        if node.right && node.right != last: # yes
            stack.append(node)
            node = node.right

            while node: # expand to find leftmost node in right subtree
                stack.append(node)
                node = node.left

        else: # no, we just came from there (or it doesn't exist)
            # delete node's contents
            node.data.cleanup()

            node.data = None # clear pointers (not really necessary)
            node.left = None
            node.right = None

            # let our parent know that it was us it just visited
            last = node
于 2012-10-13T10:58:28.507 回答
4

Blckknght 关于垃圾收集是正确的，但如果您想做一些比您的示例建议的更复杂的清理或了解您的代码为什么不起作用的情况，我将提供一个额外的答案：

你的问题似乎是elif node.left == last支票。

我不确定您的last变量用于什么或它背后的逻辑是什么。
但问题是它node.left几乎永远不等于（如果两个子节点都已设置为，则last仅将节点分配给变量，它们不适用于任何有趣的节点（那些有子节点的节点））。 lastNone

如果您查看您的代码，您会发现 ifnode.left不等于last只有右孩子被设置为None，因此只有子树的右部分被删除。

我不知道python，但这应该可行：

def delete(node):
    if node:

        # recurse: visit all nodes in the two subtrees
        delete(node.left)           
        delete(node.right)

        # after both subtrees have been visited, set pointers of this node to None
        node.left = None
        node.right = None

（我冒昧地将您的root参数重命名为node，因为赋予函数的节点不必是树的根节点。）

于 2012-10-13T11:36:03.810 回答
2

使用堆栈的迭代后序遍历可能如下所示：

def is_first_visit(cur, prev):
    return prev is None or prev.left is cur or prev.right is cur

def visit_tree(root):
    if root:
        todo = [root]
        previous = None
        while len(todo):
            node = todo[-1]
            if is_first_visit(node, previous):
                # add one of our children to the stack
                if node.left: 
                    todo.append(node.left)
                elif node.right:
                    todo.append(node.right)
                # now set previous to ourself and continue
            elif previous is node.left:
                # we've done the left subtree, do right subtree if any
                if node.right:
                    todo.append(node.right)
            else: 
                # previous is either node.right (we've visited both sub-trees)
                # or ourself (we don't have a right subtree)
                do_something(node)
                todo.pop()
            previous = node

do_something做任何你想称之为“实际删除这个节点”的事情。

您可以更简单地通过在每个节点上设置一个属性来说明它是否已经do_something调用它，但显然如果您的节点有__slots__或其他什么，并且您不想修改允许标志的节点类型。

于 2012-10-13T12:13:40.393 回答
0

我不确定你在递归调用之后对这些条件做了什么，但我认为这应该足够了：

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root = None

正如评论中所指出的，Python 不通过引用传递参数。在这种情况下，您可以像这样在 Python 中进行这项工作：

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root.left = None
    root.right = None

Usage:
delete(root)
root = None

至于迭代方法，你可以试试这个。这是伪代码，我不知道python。基本上我们进行BF搜索。

delete(root):
  make an empty queue Q
  Q.push(root)
  while not Q.empty:
    c = Q.popFront()
    Q.push(c.left, c.right)
    c = None

同样，如果您将其用作函数，则默认情况下不会修改根，但会删除所有其他节点。您可以在函数调用后将根设置为无，或者删除参数并处理全局根变量。

于 2012-10-13T11:17:52.000 回答