Как правильно вставить/удалить в двоичном дереве поиска в C?

Я как бы должен отложить свои предыдущие вопросы C, потому что этот вопрос сейчас более важен...

Я уже закодировал функции вставки и удаления в моем двоичном дереве поиска, но функция удаления не завершена. Мне нужна помощь в паре вещей...

1) Моя функция вставки хороша или ее можно как-то улучшить?

2) В моей функции удаления отсутствует удаление узла как с левым, так и с правым дочерними элементами. Я много искал за последние несколько часов, но не смог найти правильный способ сделать это.

2.a) Как удалить узел с двумя дочерними узлами?

2.b) Как и в первом вопросе, хороша ли функция удаления или ее можно улучшить? Это, я знаю, может, потому что я повторяю много кода в этих ifs, но я не вижу, как я могу его улучшить, мне тоже нужна помощь.

typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;

typedef struct sClientProfile {
    char *clientName;
    int clientAge;
    int clientNIF;
} nClientProfile;

typedef struct sClientTree {
    ClientProfile clientProfile;
    char *clientName;

    ClientTree leftTree;
    ClientTree rightTree;
} nClientTree;

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
    if(!*cTree) {
        ClientTree new = (ClientTree)malloc(sizeof(nClientTree));

        if(!new) {
            perror("malloc");
        }

        new->clientName = strdup(cProfile->clientName);
        new->clientProfile = cProfile;

        new->leftTree = NULL;
        new->rightTree = NULL;

        *cTree = new;
    } else {
        if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
            addClientToTree(&(*cTree)->leftTree, cProfile);
        } else {
            addClientToTree(&(*cTree)->rightTree, cProfile);
        }
    }
}

void deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return;

    int nCompare = strcmp((*cTree)->clientName, cName);

    if(nCompare > 0) {
        deleteClientFromTree(&(*cTree)->leftTree, cName);
    } else if(nCompare < 0) {
        deleteClientFromTree(&(*cTree)->rightTree, cName);
    } else {
        if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;
            cliPtr = NULL;

            *cTree = NULL;
        } else if(!(*cTree)->leftTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;

            *cTree = (*cTree)->rightTree;
        } else if(!(*cTree)->rightTree) {
            ClientTree cliPtr = *cTree;

            free(cliPtr->clientProfile);
            free(cliPtr);

            cliPtr->clientProfile = NULL;

            *cTree = (*cTree)->leftTree;
        } else {

            // MISSING DELETE CASE

        }
    }
}

Вы, наверное, заметили, но позвольте мне сделать два замечания:

• Это дерево использует строки вместо обычного представления типа int. Вот почему я всегда использую strcmp(), я думаю, что использую ее правильно.
• Я не использую рекурсию, я скорее передаю указатель (в данном случае указателя структуры) и работаю с ним. Как-то это выглядит более чисто, и в будущем я хочу вернуть значение успеха, если узел был удален.

ОБНОВЛЕНИЕ НИЖЕ:
Я уже сделал свою итеративную версию функции удаления, но мне не нравятся некоторые вещи в ней, может быть, их можно улучшить (или нет), но я не могу Смотри как. Я также пытался закодировать случай, когда он отсутствовал, удаляя узел с двумя дочерними элементами, но он не работает должным образом...

Я прокомментировал весь код, где, по моему мнению, код можно улучшить и в чем проблема. Я также назвал эти проблемы как A, B (Б больше нет), C и D, чтобы мы могли легко ссылаться на них.

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return FALSE;

    ClientTree currPtr = *cTree;
    ClientTree prevPtr = NULL;
    int nCompare;

    while(currPtr) {
        nCompare = strcmp(currPtr->clientName, cName);

        if(nCompare > 0) {
            prevPtr = currPtr;
            currPtr = currPtr->leftTree;
        } else if(nCompare < 0) {
            prevPtr = currPtr;
            currPtr = currPtr->rightTree;
        } else {
            /*
             * A)
             * 
             * The following cases have 3 lines in common, the free()
             * calls and return statement. Is there anyway to improve
             * this code and make it more compact?
             * 
             * Of course, the printf's are to be removed...
             */
            if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
                printf("CASE #1\n");

                *cTree = NULL;

                free(currPtr->clientProfile);
                free(currPtr);

                return TRUE;
            } else if(!currPtr->leftTree || !currPtr->rightTree) {
                printf("CASE #2\n");

                if(prevPtr->leftTree == currPtr) {
                    prevPtr->leftTree = currPtr->rightTree;
                } else {
                    prevPtr->rightTree = currPtr->leftTree;
                }

                free(currPtr->clientProfile);
                free(currPtr);

                return TRUE;
            } else {
                printf("CASE #3\n");

                ClientTree tempPtr = currPtr->rightTree;

                while(tempPtr->leftTree) {
                    tempPtr = tempPtr->leftTree;
                }

                /*
                 * C)
                 * 
                 * This has a big problem...
                 * 
                 * If you take a look at the ClientProfile structure,
                 * in the first post, you'll see two ints
                 * (clientNIF/clientAge) and one char* (clientName).
                 * 
                 * The problem is that the following code line is only
                 * copying the integer data, not the string. For some
                 * reason, the string remains the old one.
                 * 
                 * I tried to use strdup() directly on clientName like:
                 * currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
                 * but it still doesn't work.
                 * 
                 * Why everything is being copied but the strings?
                 */
                currPtr->clientProfile = tempPtr->clientProfile;

                /*
                 * D)
                 * 
                 * Is there anyway to not call the function itself
                 * and make the while loop once again and delete the
                 * corresponding leaf?
                 */
                return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
            }
        }
    }

    return FALSE;
}