如何删除二进制搜索树的所有节点 [英] How to delete all nodes of a Binary Search Tree

问题描述

我正在尝试编写代码以删除BST的所有节点(每个节点只有三个属性，left，right和data，没有父指针).下面的代码是我想出的，它仅删除树的右半部分，而保留左半部分不变.我该如何修改它，以使左半部分也被删除(以便最终我只剩下没有左子树或右子树的根节点)?

I am trying to write a code to delete all nodes of a BST (each node has only three attributes, left, right and data, there are no parent pointers). The following code is what I have come up with, it deletes only the right half of the tree, keeping the left half intact. How do I modify it so that the left half is deleted as well (so that ultimately I am left with only the root node which has neither left or right subtrees)?

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

其次，有人可以使用堆栈或其他相关数据结构来建议一种迭代方法吗?

And secondly, can anybody suggest an iterative approach as well, using stack or other related data structure?

推荐答案

Blckknght关于垃圾回收是正确的，但是如果您想执行比示例所建议的更为复杂的清理工作，或者理解为什么您的代码不起作用，我会提供其他答案:

Blckknght is right about garbage collection, but in case you want to do some more complex cleanup than your example suggests or understand why your code didn't work, i'll provide an additional answer:

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

Your problem seems to be the elif node.left == last check.

我不确定您的last变量用于什么或它背后的逻辑.
但是问题在于，node.left几乎永远不会等于last(如果两个子级都已经设置为None，则仅将节点分配给last变量，而对于任何有趣的节点，它们都不是. (那些有孩子的人).

I'm not sure what your last variable is used for or what the logic is behind it.
But the problem is that node.left is almost never equal to last (you only assign a node to the last variable if both children are already set to None, which they aren't for any of the interesting nodes (those that have children)).

如果您查看代码，将会看到，如果node.left不等于last，则仅将正确的子代设置为None，因此子树的仅右侧部分被设置为None.已删除.

If you look at your code, you'll see that in that if node.left isn't equal to last only the right child gets set to None, and thus only the right part of the subtree is deleted.

我不了解python，但这应该可以工作:

I don't know python, but this should work:

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，因为赋予该函数的节点不必是树的根节点.)

(I took the liberty of renaming your root parameter to node, since the node given to the function doesn't have to be the root-node of the tree.)

这篇关于如何删除二进制搜索树的所有节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！