如何在Python中修剪子树

发布于 2024-12-01 22:23:48 字数 301 浏览 2 评论 0原文

我（仍然）正在处理 Python 程序中的树结构。树中的每个节点都有一个字典“children”，其键保存弧信息，值是子节点。（每个节点都有一个（parent，parent_arc）对，其中parent是其父节点，parent_arc是父节点链接该节点的弧。）

现在我想修剪一棵子树，其根是节点的子节点N. 假设这个孩子是 N.children[a]。

del N.children[a] 根本不会释放子树占用的内存。我是否必须实现一种方法来删除子树中的每个节点？我该怎么做？我是否需要重新定义节点类以实现高效的子树修剪？

谢谢你！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十雾 2024-12-08 22:23:48

当A->时B和B-> A 你有参考周期。解决这个问题的一个好方法是让子级使用弱引用来指向父级。像这样的事情：

import weakref
class Node():
    parent = None
    child = None
    @property
    def parent(self):
        parent = self._parent()
        if parent is not None:
            return parent
        raise ValueError("parent has been deleted")
    @parent.setter     # python 2.6+
    def parent(self, parent):
        self._parent = weakref.ref(parent)

现在，该节点没有与其父节点的直接链接，当您删除子节点时，它确实会消失*。（您可能需要对parent_arc使用相同的方法。）

*请注意，即使Python在不存在引用循环的情况下会更快地释放对象，但它可能不会将该内存返还给操作系统。

When A -> B and B -> A you have reference cycles. A good way to get around that is to have the children use weak references to point back to the parent. Something like this:

import weakref
class Node():
    parent = None
    child = None
    @property
    def parent(self):
        parent = self._parent()
        if parent is not None:
            return parent
        raise ValueError("parent has been deleted")
    @parent.setter     # python 2.6+
    def parent(self, parent):
        self._parent = weakref.ref(parent)

Now, the node does not have a direct link to its parent, and when you delete the child it really will go away*. (You may need to use the same method for the parent_arc.)

*Note that even though Python will release the objects more quickly if no reference cycles exist, it may not give that memory back to the OS.

回复收藏 0 原文

~没有更多了~