C++ 二叉树上的递归删除

recursive delete on a binary tree

提问by Simon Righley

I am trying to understand how the recursive method of deletion of a binary search tree works. The code that I came across in many places looks as follows:

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

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

I can't understand however a) how does it work if there are no returns in the routine? b) when free() gets to be called? I think about, e.g., such a tree:

但是，我无法理解 a) 如果例程中没有返回，它是如何工作的？b) 什么时候调用 free()？我想，例如，这样一棵树：

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

So my understanding is that I traverse 10->6->5, and then I call destroy_tree(5->left). Therefore, leaf inside if is NULL, and what is if-dependent is not executed, hence 5 is not being deleted. Where do I make mistake in this reasoning? How does winding and unwinding work here? Any help kindly appreciated :-)

所以我的理解是遍历10->6->5，然后调用destroy_tree(5->left)。所以if里面的leaf是NULL，if-dependent的东西不会被执行，所以5不会被删除。我在这个推理中哪里出错了？收卷和放卷在这里是如何工作的？任何帮助表示赞赏:-)

回答by mark

It looks like this at that point:

那个时候看起来是这样的：

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

Nothing is required to return... the "history" of the steps is on the call stack, which looks something like this at that point:

不需要返回任何东西......步骤的“历史”在调用堆栈上，此时看起来像这样：

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

So after leaf_5 is gone, it goes back up the stack and does destroy_tree(leaf_6->right, which is leaf_8)... etc...

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

回答by Zzz

This is how the function basically works:

这是该功能的基本工作方式：

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

Below is code for how a full implementation of recursive delete should look:

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

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