eliminazione ricorsiva su un albero binario

Question

Sto cercando di capire come funziona il metodo ricorsivo di eliminazione di un albero di ricerca binario. Il codice che mi sono imbattuto in molti luoghi si presenta come segue:

void destroy_tree(struct node *leaf) 
{ 
    if(leaf != 0) 
    { 
     destroy_tree(leaf->left); 
     destroy_tree(leaf->right); 
     free(leaf); 
    } 
} 

non riesco a capire però a) come funziona se non ci sono ritorni nella routine? b) quando viene chiamato free()? Penso, per esempio, un tale albero:

      10 
         / \ 
         6  14 
        /\ /\ 
         5 8 11 18 

Quindi la mia comprensione è che posso attraversarla 10-> 6-> 5, e poi chiamo destroy_tree (5-> a sinistra). Pertanto, leaf inside se è NULL e cosa è if-dependent non viene eseguito, quindi 5 non viene eliminato. Dove sbaglio in questo ragionamento? Come funzionano gli avvolgimenti e lo svolgimento? Qualsiasi aiuto gentilmente apprezzato :-)

Answer 1

Ecco come si presenta a questo punto: è necessario

void destroy_tree(struct node *leaf_5) 
{ 
    if(leaf_5 != 0) // it's not 
    { 
     destroy_tree(leaf_5->left); // it's NULL so the call does nothing 
     destroy_tree(leaf_5->right); // it's NULL so the call does nothing 
     free(leaf_5); // free here 
    } 
} 

Niente di tornare ... la "storia" dei passi è sul stack di chiamate, che sembra qualcosa in questo modo, a quel punto:

destroy_tree(leaf_10) 
    destroy_tree(leaf_10->left, which is leaf_6) 
    destroy_tree(leaf_6->left, which is leaf_5) 

Così, dopo leaf_5 è andato, risale lo stack e fa destroy_tree(leaf_6->right, which is leaf_8) ... ecc ...

Answer 2

questo è come la funzione fondamentalmente wor KS:

void destroy_tree(struct node *leaf) 
{ 
    if(leaf_5 != 0) // it's not 
    { 
     destroy_tree(leaf->left); 
     // Traverse the tree all the way left before any of the code below gets executed. 
     destroy_tree(leaf->right); 
     // Traverse the tree all the way right from the final left node before any of 
     //the code below gets executed 
     free(leaf); // Free the final node 
    } 
} 

Di seguito è riportato il codice per come un'implementazione completa di cancellazione ricorsiva dovrebbe apparire:

void DeleteNode(TreeNode*& tree); 
void Delete(TreeNode*& tree, ItemType item); 
void TreeType::DeleteItem(ItemType item) 
// Calls the recursive function Delete to delete item from tree. 
{ 
Delete(root, item); 
} 
void Delete(TreeNode*& tree, ItemType item) 
// Deletes item from tree. 
// Post: item is not in tree. 
{ 
if (item < tree->info) 
Delete(tree->left, item); // Look in left subtree. 
else if (item > tree->info) 
Delete(tree->right, item); // Look in right subtree. 
else 
DeleteNode(tree); // Node found; call DeleteNode. 
} 


void GetPredecessor(TreeNode* tree, ItemType& data); 
void DeleteNode(TreeNode*& tree) 
// Deletes the node pointed to by tree. 
// Post: The user's data in the node pointed to by tree is no 
// longer in the tree. If tree is a leaf node or has only one 
// non-NULL child pointer, the node pointed to by tree is 
// deleted; otherwise, the user's data is replaced by its 
// logical predecessor and the predecessor's node is deleted. 
{ 
ItemType data; 
TreeNode* tempPtr; 
tempPtr = tree; 
if (tree->left == NULL) 
{ 
tree = tree->right; 
delete tempPtr; 
} 
else if (tree->right == NULL) 
{ 
tree = tree->left; 
delete tempPtr; 
} 
else 
{ 
GetPredecessor(tree->left, data); 
tree->info = data; 
Delete(tree->left, data); // Delete predecessor node. 
} 
} 

void GetPredecessor(TreeNode* tree, ItemType& data) 
// Sets data to the info member of the rightmost node in tree. 
{ 
while (tree->right != NULL) 
tree = tree->right; 
data = tree->info; 
}