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

以下是我的二叉搜索树的删除结点函数，无法正确删除结点，请问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，其他函数均无问题

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

递归的写法，供参考：

#include <stdio.h>
typedef struct _TreeNode{
    //结点结构体
    int    data;
    struct _TreeNode* lchild;
    struct _TreeNode* rchild;
}TreeNode, *PTreeNode;

PTreeNode findMaxNode(PTreeNode root) {
    // 找最大值,往左走一步,然后一路往右走到头
    PTreeNode res = root->lchild;
    while (res->rchild != NULL) {
        res = res->rchild;
    }
    return res;
}

PTreeNode findMinNode(PTreeNode root) {
    // 找最小值,往右走一步,然后一路往左走到头
    PTreeNode res = root->rchild;
    while (res->lchild != NULL) {
        res = res->lchild;
    }
    return res;
}

PTreeNode deleteNode(PTreeNode root, int data)
{
    // 处理当前节点
    if (root == NULL)
         return NULL;
    if (root->data == data) {
            // 如果两个子节点都是null,说明是叶子节点,直接删除即可
        if (root->lchild == NULL && root->rchild == NULL) {
            root = NULL;
        } else if (root->rchild != NULL) {
            // 如果右子树不为空,找到后继节点,替换
            root->data = findMinNode(root)->data;
            root->rchild = deleteNode(root->rchild, root->data);
        } else {
            // 如果左子树不为空,找到前驱节点,替换
            root->data =  findMaxNode(root)->data;
            root->lchild = deleteNode(root->lchild, root->data);
        }
    } else if (data < root->data) {
        // 处理左子树
        root->lchild = deleteNode(root->lchild, data);
    } else {
        // 处理右子树
        root->rchild = deleteNode(root->rchild, data);
    }
    return root;
}

76行f可为空，改为!f

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};