rekursives Löschen auf einem Binärbaum

Question

Ich versuche zu verstehen, wie die rekursive Methode der Löschung eines binären Suchbaums funktioniert. Der Code, den ich kam in vielen Orten sieht wie folgt aus:

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

Ich kann jedoch nicht a) verstehen, wie es funktioniert, wenn es keine Rückkehr in der Routine ist? b) wann soll free() aufgerufen werden? Ich denke über, zum Beispiel, wie ein Baum:

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

Also mein Verständnis ist, dass ich 10-> 6-> 5, durchqueren und dann rufe ich destroy_tree (5-> links). Daher ist leaf inside if NULL, und was if-abhängig ist, wird nicht ausgeführt, daher wird 5 nicht gelöscht. Wo mache ich Fehler in dieser Argumentation? Wie funktioniert das Auf- und Abwickeln? Jede Hilfe freundlich geschätzt :-)

Answer 1

es so an diesem Punkt sieht:

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

Nichts erforderlich ist, um zurückzukehren ... die „Geschichte“ der Schritte auf dem Call-Stack, das etwas aussieht dies wie an diesem Punkt:

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

So nach leaf_5 weg ist, geht es zurück Stapel und tut destroy_tree(leaf_6->right, which is leaf_8) ... etc ...

Answer 2

Dies ist, wie die Funktion grundsätzlich 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 
    } 
} 

Im Folgenden finden Sie Code, wie eine vollständige Implementierung der rekursiven löschen aussehen sollte:

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