Annullare un valore da un puntatore

Non ho fatto l’aritmetica dei puntatori da molto tempo, quindi ho pensato di provare la mia mano a C e fare un semplice albero di ricerca binaria. Non riesco a ottenere il blocco della cancellazione, tuttavia. Qualcosa in questo senso funziona come mi aspetto:

typedef struct Node{ int value; struct Node *left; struct Node *right; }Node; typedef struct Tree{ struct Node* root; }Tree; int main(){ Tree *tree = createTree(); treeInsert(10, tree); // Inserts 10 at root treeInsert(30, tree); // Inserts 30 to root->right treeInsert(5, tree); // Inserts 5 to root->left treeInsert(7, tree); // Inserts 7 to root->left->right treeInsert(12, tree); // Inserts 12 to root->right->left // Removes Node "7" from the tree successfully free(tree->root->left->right); // Free memory for this node in the tree tree->root->left->right = NULL; // Set the pointer to NULL return 0; } 

Mi piacerebbe scrivere una funzione nodeDelete(Node *killNode) per liberare la memoria associata a un nodo, quindi nodeDelete(Node *killNode) su NULL, ma trovo che non funzioni come mi aspetto.

 int main(){ // ... snip ... Node *kill = tree->root->left->right // Points kill node to Node "7" free(kill); // Deallocates memory kill = NULL; // Points kill to NULL, but keeps // tree->root->left->right **undefined** // ... snip ... } 

Penso che il mio problema è che sto dicendo che kill ora punta a NULL, che lo disconnette dal nodo nell’albero e non influenza il puntatore del nodo originale. Come posso dire che voglio puntare su tree->root->left->right su NULL invece di kill ? Ho bisogno di un puntatore a un puntatore in questo caso?

Sì, se si desidera eliminare quel nodo è necessario impostare tree->root->left->right su NULL . Ciò significa che non puoi semplicemente passare il valore di quel puntatore alla funzione di cancellazione.

Hai due opzioni: puoi passare un puntatore al genitore del nodo da eliminare, insieme alle informazioni su quale bambino eliminare:

 nodeDelete(Node *parent, int kill_right) { Node *kill; if (kill_right) { kill = parent->right; parent->right = NULL; } else { kill = parent->left; parent->left = NULL; } free(kill); } 

In questo caso chiameresti nodeDelete(tree->root->left, 1); .

In alternativa puoi passare un puntatore al puntatore che vuoi rimuovere:

 nodeDelete(Node **killptr) { free(*killptr); *killptr = NULL; } 

In questo caso chiameresti nodeDelete(&tree->root->left->right); .

Sì, è necessario utilizzare un doppio puntatore. Ti consigliamo inoltre di eliminare in modo ricorsivo eventuali figli del nodo che stai eliminando:

 void nodeDelete(Node **killNode) { if(!*killNode) return; // Free child nodes nodeDelete((*killNode)->left); nodeDelete((*killNode)->right); // Free the node itself free(*killNode); *killNode=NULL; } 

Il controllo del puntatore nullo viene intenzionalmente eseguito all’inizio – questo impedisce di dover avvolgere le chiamate ricorsive nel controllo del puntatore nullo.