二叉搜索树删除结点代码存在问题

Question

以下是我的二叉搜索树的删除结点函数，无法正确删除结点，请问bug在哪里？如何解决

typedef struct _TreeNode
{
    //结点结构体
    int data;
    struct _TreeNode* lchild;
    struct _TreeNode* rchild;
}TreeNode, *PTreeNode;

void delete_node(PTreeNode* root, int data)
{
    //删除结点
    PTreeNode* p = root;
    PTreeNode* f = NULL;
    PTreeNode* q = NULL;
    PTreeNode* s = NULL;
    if (!*root)
    {
        return;
    }
    while (*p)
    {
        if ((*p)->data == data)
        {
            break;
        }
        f = p;
        if ((*p)->data > data)
        {
            p = &((*p)->lchild);
        }
        else
        {
            p = &((*p)->rchild);
        }
    }
    if (*p == NULL)
    {
        return;
    }
    if (((*p)->lchild) && ((*p)->rchild))
    {
        //左右结点都非空
        q = p;
        s = &((*p)->lchild);
        while((*s)->rchild)
        {
            //遍历p的前驱结点
            q = s;
            s = &((*s)->rchild);
        }
        (*p)->data = (*s)->data;
        if (q != p)
        {
            (*q)->rchild = (*s)->lchild;
        }
        else
        {
            (*q)->lchild = (*s)->lchild;
        }
        free(*s);
    }
    else
    {
        if (!(*p)->rchild)
        {
            //右子树无结点
            q = p;
            p = &((*p)->lchild);
        }
        else if (!(*p)->lchild)
        {
            //左子树无结点
            q = p;
            p = &((*p)->rchild);
        }
        if (!*f)
        {
            root = p;
        }
        else if (q == &((*f)->lchild))
        {
            (*f)->lchild = *p;
        }
        else
        {
            (*f)->rchild =*p;
        }
        free(*q);
    }
}

运行结果:

测试用例1 5 6 8 0，删除完只输出1，其他函数均无问题

Answer 1

看下这篇博客，也许你就懂了，链接：二叉搜索树详解（附代码）