バイナリツリーの再帰的削除

Question

バイナリ検索ツリーの削除の再帰的な方法がどのように機能するかを理解しようとしています。私は多くの場所で出会ったコードは次のようになります。

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

私は日常的にはリターンが存在しない場合a）はどのように動作しますが理解できないのですか？ b）free（）が呼び出されると、？

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

だから、私の理解は、私は> 5 10-> 6を通過した後、私は（左5>）destroy_treeを呼び出すことです：私は、例えば、このようなツリー、考えます。したがって、if内部のleafはNULLで、if-dependentは実行されないため、5は削除されません。この理由で私はどこで間違いを犯すのですか？ここで巻き取りと巻き戻しはどのように機能しますか？親切

Answer 1

:-)感謝すべてのヘルプは、それはその時点で次のようになります。何も返す必要はありません

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

...ステップの「歴史」が何かを探しますコールスタック、上にありますその時点で、次のように：leaf_5がなくなった後

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

だから、それはスタックまで戻ってdestroy_tree(leaf_6->right, which is leaf_8) ...などを行います...

Answer 2

これはどのように機能基本的にWORですKS：

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