Удаление дерева (структуры данных) в 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?

(то есть, есть ли способ сделать delete(node) вместо parent.left = None в Python

Разъяснение:. Я хотел бы удалить дерево, как следующее (там могут быть некоторые ошибки) в 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 мне нужна ссылка на родительский элемент узла, чтобы удалить узел. Существует ли более простой способ, чем мой код для удаления определенного узел из дерева?

Answer 1

Как поясняется в комментариях, в Python нет необходимости. Но если вы хотите код Python, который «действует как» код C, здесь вы идете:

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. Все, что вы можете сделать - и все, что вам нужно сделать, - это прекратить ссылки на объекты, которые вам больше не нужны.

Edit: и, я должен добавить, вы будете в конечном итоге думаю, что это хорошая вещь: жизнь Soooooo гораздо приятнее, когда вы знаете, что вы никогда не увидите NULL разыменования указателя Segfault снова ;-) И это действительно «почему» у Python нет возможности написать «освободить эту память».

Answer 2

Я думаю, что у вас есть небольшое непонимание различий в управлении памятью на C и Python. На языке C вам нужно удалить всю неиспользуемую память, которая ранее была взята из кучи. Вы можете сделать это, вызвав функцию free.
Python использует garbage collection для автоматического управления памятью. Итак, сделав parent.left = None, вы говорите: ссылка на этот объект будет None, никто не знает ссылки на этот объект, мы можем его собрать. Сборщик мусора обрабатывает все остальное, поэтому вам не нужно явно удалять этот объект из кучи.

Есть ли более простой способ, чем мой код для удаления определенного узла из дерева?

Вы не удаляете определенный узел из своего дерева, вы сами удаляете его. У вас есть более легкий подход сделать это в Python - просто установите ссылку на его корень на None, и сборщик мусора позаботится о дереве.

Answer 3

Я предполагаю, что вы ищете:

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