usuwanie rekursywne na drzewie binarnym

Question

Próbuję zrozumieć, jak działa rekurencyjna metoda usuwania drzewa wyszukiwania binarnego. Kod, który natknąłem się w wielu miejscach wygląda następująco:

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

nie mogę zrozumieć jednak), jak to działa, jeśli nie ma żadnych zwrotów w rutynę? b) kiedy zostanie wywołany free()? Myślę o, na przykład takiego drzewa:

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

Więc mój zrozumienia jest to, że przechodzą 10-> 6-> 5, a następnie zadzwonić destroy_tree (5-> lewo). Z tego powodu, jeśli jest to NULL, to należy je zapisać, a co nie jest zależne, jeśli nie jest wykonywane, stąd 5 nie jest usuwane. Gdzie popełniam błąd w tym rozumowaniu? Jak tu działa zwijanie i odwijanie? Każda pomoc uprzejmie ceniona :-)

Answer 1

Wygląda to w tym momencie:

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 
    } 
} 

Nic nie jest wymagane, aby wrócić ... „Historia” z etapów jest na stosie wywołań, który wygląda mniej jak to w tym momencie:

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

Więc po leaf_5 znika, wraca w górę stosu i robi destroy_tree(leaf_6->right, which is leaf_8) ... etc ...

Answer 2

ten sposób funkcja zasadzie 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 
    } 
} 

Poniżej jest kod na jak pełne wdrożenie rekurencyjnych usuwać powinien wyglądać:

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; 
}