Recursively deletes subtrees rooted in x in a binary tree
- 2020-06-15 09:55:37
- OfStack
Name: Delete a subtree rooted in x in a 2-tree
Note: this procedure for the majority of the content, comments are explained in more detail. One thing to mention here is that the recursive function flag passes not the reference mentioned in the previous article, but a normal variable, because when passing a parameter down (whether the current node is x or not), it only passes to the corresponding subtree, not to the node of the entire tree. The next article will summarize the recursive passing parameters.
// Recursive delete 2 Cross in the tree x Is the subtree of the root, ( flag Marked)
int DelRoot_x(BiTree &T, int x,int flag)
{
if(T == NULL)
return 0;
else
{
if(T->data == x) // If the value of the current node is x , change the flag bit, which is passed to the recursive subfunction below flag value
{
flag = 1;
}
int lef_ret = DelRoot_x(T->lchild,x,flag); // Recursively left subtree, lef_ret Is the information returned from the left subtree
int rig_ret = DelRoot_x(T->rchild,x,flag); // Recursive right subtree, rig_ret Is the information returned from the right subtree
if(1 == flag) // If the mark is 1 , indicating that there is x In other words, the current node needs to be deleted
{
if(T->data == x) // If it is x The node needs to pass information to the upper node so that its parent nullifies the corresponding pointer field
return 1;
delete T;
}
else
{
if(1 == lef_ret) // Receives information from a child if its child is x , its pointer field needs to be nulled
T->lchild = NULL;
if(1 == rig_ret ) // Receives information from a child if its child is x , its pointer field needs to be nulled
T->rchild = NULL;
}
}
return 0;
}
conclusion