如何删除二进制搜索树的所有节点

4 回答

• 2

  Blckknght对垃圾收集是正确的，但是如果你想做一些比你的例子建议更复杂的清理或者理解为什么你的代码不起作用，我会提供一个额外的答案：

  您的问题似乎是 elif node.left == last 检查 .

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

  如果查看代码，您会看到，如果 node.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 ，因为赋予该函数的节点不必是树的根节点 . ）

  回复于 2024-04-26T19:43:49+08:00
• 4

  如果要删除两个子树，则无需递归 . 只需将 root.left 和 root.right 设置为 None 并让垃圾收集器处理它们 . 实际上，你可以设置 root = None 而不是首先制作一个 delete 函数！

  Edit: 如果你需要在数据值上运行清理代码，你可能想要通过树递归来获取所有这些代码，如果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
  

  回复于 2024-04-26T19:43:49+08:00
• 4

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

  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 会执行您想要调用的任何内容"actually deleting this node" .

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

  回复于 2024-04-26T19:43:49+08:00
• 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
  

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

  回复于 2024-04-26T19:43:49+08:00