二叉树上的递归删除

我试图理解删除二叉搜索树的递归方法是如何工作的。 我在很多地方遇到的代码如下：

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 

所以我的理解是我遍历10-> 6-> 5，然后我调用destroy_tree（5->左）。 因此，leaf if if为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 } } 

没有必要返回…步骤的“历史”在调用堆栈上，在这一点看起来像这样：

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

所以在leaf_5消失之后，它会回到堆栈并执行destroy_tree(leaf_6->right, which is leaf_8) ……等等……

Answer 2

这是函数基本上如何工作：

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

下面是如何完整实现递归删除的代码：

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