Python中删除树（数据结构）

Question

以下是在C语言中删除一棵树的代码（由GeeksforGeeks提供）：

#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
struct node 
{
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data) 
{
    struct node* node = (struct node*)
                           malloc(sizeof(struct node));

    node->data = data;
    node->left = NULL;
    node->right = NULL;  
    return(node);
}

/*  This function traverses tree in post order to 
    to delete each and every node of the tree */
void deleteTree(struct node* node) 
{
    if (node == NULL) return;

    /* first delete both subtrees */
    deleteTree(node->left);
    deleteTree(node->right);

    /* then delete the node */
    printf("\n Deleting node: %d", node->data);
    free(node);
} 


/* Driver program to test deleteTree function*/   
int main()
{
    struct node *root = newNode(1); 
    root->left            = newNode(2);
    root->right          = newNode(3);
    root->left->left     = newNode(4);
    root->left->right   = newNode(5); 

    deleteTree(root);  
    root = NULL;

    printf("\n Tree deleted ");

    getchar();
    return 0;
}
The above deleteTree() function deletes the tree, but doesn’t change root to NULL which may cause problems if the user of deleteTree() doesn’t change root to NULL and tires to access values using root pointer. We can modify the deleteTree() function to take reference to the root node so that this problem doesn’t occur. See the following code.

#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                           malloc(sizeof(struct node));

    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

在C语言中，可以通过free(node)删除节点。但在Python中，并没有这样的方法。在Python中，我是否需要一个指向节点父节点的引用来删除节点，而在C中则不需要？

（即，在Python中是否有一种方法可以执行delete(node)而不是parent.left = None？） 澄清： 我想在Python中删除如下所示的树（可能存在一些错误）。

def delete_tree(root, parent):
    if not root:
        return
    if not root.left and not root.right:
        if root is parent.left:
            parent.left = None
        else:
            parent.right = None
    delete_tree(root.left, root)
    delete_tree(root.right, root)
    root = None

在提供的C代码中，可以通过释放特定节点分配的内存来删除节点。然而，在Python中，我需要一个指向节点父级的引用来删除节点。有没有比我的代码更简单的方法从树中删除特定的节点？

- Maximus S

---

不清楚你想要实现什么：Python使用垃圾回收 - 永远不需要显式释放对象。如果你完成了一棵树，它的内存将在最后一个对该树的引用消失后自动回收。 - Tim Peters

@TimPeters 这是真的吗？即使实现了 __del__ 并且可能存在循环引用？ - Hyperboreus

@MaximusS，抱歉，我仍然不明白你想要实现什么。Python既没有malloc()也没有free()。忘记它们的存在，你会更开心;-)“如何在Python中删除一棵树？”你不需要这样做。当你的程序停止引用它时，它会自动消失。如果你愿意，你可以浪费时间将东西设置为None，但这并不是必要的。 - Tim Peters

@TimPeters 我之所以问这个问题，是因为文档中的这段话："一个对象列表，收集器发现它们是不可达的但无法被释放（不可回收的对象）。默认情况下，此列表仅包含具有 del() 方法的对象。26.1 具有 del() 方法并且是引用循环的一部分的对象会导致整个引用循环无法回收，包括不一定在循环中但只能从循环中访问的对象。Python 不会自动收集这样的循环，因为通常情况下，Python 无法猜测运行 del() 方法的安全顺序。" - Hyperboreus

@Hyperboreus，是的，__del__方法可能会创建永久循环垃圾。但在下一个Python 3版本中，它们将不再这样了 :-) - Tim Peters

Answer 1

如评论所解释的，Python中不需要这样做。但是，如果您想要像C代码一样工作的Python代码，那么请看以下代码：

class Node:
    # with data members .data, .left, and .right
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

def deleteTree(node):
    if node is not None:
        deleteTree(node.left)
        deleteTree(node.right)
        node.left = node.right = None

在Python中，不可能拼写“释放此内存”。你能做的，也是你需要做的，就是停止引用你不再关心的对象。

补充说明: 而且，我应该补充说，最终你会认为这是一件好事：当你知道你再也不会看到空指针解除引用段错误时，生活会更加愉快；-）这就是为什么Python没有释放内存的方法的真正原因。

- Tim Peters

Answer 2

我认为你对C和Python中内存管理的差异有些误解。在C语言中，您需要删除先前从堆中获取的所有未使用的内存。您可以通过调用free函数来实现。
Python使用垃圾回收进行自动内存管理。因此，通过执行parent.left = None，您告诉Python：对该对象的引用将是None，没有其他人知道该对象的引用，我们可以回收它。垃圾回收器处理其他所有内容，因此您不需要显式地从堆中删除此对象。

是否有比我的代码更简单的方法来从树中删除特定节点？

您并没有删除树中的特定节点，而是删除了整个树。在Python中，您有更简单的方法-只需将对其根的引用设置为None，垃圾回收器就会处理树。

- aga

---

谢谢您再次回复。我明白你的意思，但这不是我想问的。你能看一下更新吗？ - Maximus S

嘿，谢谢你！现在我意识到“删除一棵树”的问题只在C语言中有难度，而且这个问题实际上并不适用于Python。 - Maximus S

Answer 3

我猜你在寻找的是：

node ##class '__main__.node'
del(node)
node
Traceback (most recent call last):
NameError: name 'node' is not defined

- Rahul Bhambri