> 文档中心 > 二叉树递归删除节点操作超详细图解说明。

二叉树递归删除节点操作超详细图解说明。

递归函数来删除节点,最主要的是函数调用的返回,明白函数调用时的位置和参数传递时形参是实参的初始化的理解。

删除节点。
1)如果需要删除的节点有左子树(不管有没有右子树),其方法是将左子树中最大值替换掉该节点。

第一步:通过递归寻找到需要删除的节点。
第二步:找到删除的那个节点的左子树的最大值。
第三步:将这个最大值替换需要删除的节点。
第四步:通过调用删除函数,递归地去删除这个最大值。(不能直接删除,需要递归删除,因为这个节点虽然肯定没有右子树(因为如果有右子树,该节点就不是最大的),但是有可能有左子树)

2)如果需要删除的节点只有右子树,其方法就是把右子树中最小值替换该节点。

第一步:通过递归寻找到需要删除的节点。
第二步:找到删除的那个节点的右子树的最小值。
第三步:将这个最小值替换需要删除的节点。
第四步:通过调用删除函数,递归地去删除这个最小值。(不能直接删除,需要递归删除,因为这个节点虽然肯定没有左子树(因为如果有左子树,该节点就不是最小的),但是有可能有右子树)

3)如果需要删除的节点的度为0,则直接删除。

第一步:通过递归寻找到需要删除的节点。
第二步:直接调用free()释放该节点的空间。

------------------------------------------------------
struct node *delete_node(struct node *root,int num)
{
    //1. 找到底都没有找到该节点,则直接返回NULL。
    if(root == NULL)
        return NULL;
    
    //2. 通过递归寻找到需要删除的节点。
    if(num data)  //应该继续去左边找
    {
        root->lchild = delete_node(root->lchild,num);
    }
    else if(num > root->data)  //应该继续去右边找
    {
        root->rchild = delete_node(root->rchild,num);
    }
    else{  //找到你想删除的节点,这个节点就是root
        //3. 判断需要删除的节点有没有左子树
        struct node *tmp = NULL;
        if(root->lchild != NULL)  //不为NULL,说明有左子树
        {
            //4. 寻找该节点左子树的最大值。
            for(tmp=root->lchild;tmp->rchild!=NULL;tmp=tmp->rchild);
            
            //从循环出来时,tmp就是左子树的最大值。
            
            //5. 将tmp指向数据赋值给需要删除的节点的数据域。
            root->data = tmp->data;
            
            //6. 递归删除这个tmp
            root->lchild = delete_node(root->lchild,tmp->data);    
        }
        else if(root->rchild!=NULL)  //不为NULL,说明有右子树
        {
            //4. 寻找该节点右子树的最小值。
            for(tmp=root->rchild;tmp->lchild!=NULL;tmp=tmp->lchild);
            
            //从循环出来时,tmp就是右子树的最小值。
            
            //5. 将tmp指向的数据赋值给需要删除的节点的数据域
            root->data = tmp->data;
            
            //6. 递归删除这个tmp
            root->rchild = delete_node(root->rchild,tmp->data);
        }
        else{
            free(root);
            return NULL;  //最后的节点释放掉之后,一定要返回一个NULL给指向这个最后的节点的左/右指针。    
        }
    }
    
    return root;

}

代码详细流程图解