// 哪些变量定义语义不清，我给改过来。
//  删除操作函数已经修改好，简单测试了一下，没发现问题了，欢迎大家继续测试
//  因时间问题，代码仍未精简、完善, 见谅！
//  测试时可以输入字母a、b、c、d...代替输入月份

void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点！\n");
        return ;
    }
    if(strcmp(x.key, (*parent)->data.key) == 0){
        if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL))
        {    //情况1：无孩子 
            free(*parent);
            *parent = NULL;
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL))
        {    //情况2：无左孩子 
            temp = *parent;
            *parent = (*parent)->rightChild;
            free(temp);
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL))
        {    //情况3：无右孩子 
            temp = *parent;
            *parent = (*parent)->leftChild;
            free(temp);
             *unbalanced = TRUE;
        }else{    //情况4：有俩孩子 
            if((*parent)->leftChild->rightChild == NULL){//左孩无右孙 
                temp = *parent;
                *parent = (*parent)->leftChild;
                (*parent)->rightChild = temp->rightChild;
                free(temp);
                if((*parent)->bf == 0){
                    (*parent)->bf = -1;
                    *unbalanced == FALSE;
                }else if((*parent)->bf == 1){
                    (*parent)->bf = 0;
                     *unbalanced = FALSE;
                }else{
                    rightRotation(parent, unbalanced);
                }
            }else{    //左孩有右孙 
                leftMaxNode(parent, &(*parent)->leftChild, unbalanced);
                 if(*unbalanced){
                    if((*parent)->bf == -1){
                        rightRotation(parent, unbalanced);
                    }else if((*parent)->bf == 0){
                        (*parent)->bf = -1;
                        *unbalanced = FALSE;
                    }else if((*parent)->bf == 1){
                        (*parent)->bf = 0;
                        *unbalanced = FALSE;
                    } 
                }    
            }
        }
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlDelete(&(*parent)->leftChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == 1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = -1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == -1){
                rightRotation(parent, unbalanced);
            }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlDelete(&(*parent)->rightChild, x, unbalanced);
        if(*unbalanced)   
            if((*parent)->bf == -1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            }
    }
}

void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced)
{            /* 与左子树最大元交换，并删除结点 */
    if((*maxNode)->rightChild->rightChild == NULL){
        treePointer temp = *parent;
        
        *parent = (*maxNode)->rightChild;
        (*maxNode)->rightChild = (*maxNode)->rightChild->leftChild;
        (*parent)->leftChild = temp->leftChild;
        (*parent)->rightChild = temp->rightChild;
        (*parent)->bf = temp->bf;
        free(temp);
        temp = NULL;/*不知道为什么，这里必须给temp赋空值，虽然后再不用temp了*/ 
        if((*maxNode)->bf == 0){
            (*maxNode)->bf = -1;
            *unbalanced = FALSE;
        }else if((*maxNode)->bf == -1){
            (*maxNode)->bf == 0;
            *unbalanced = TRUE;
        }else if((*maxNode)->bf == 1){
            leftRotation(maxNode, unbalanced);
            (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
        }   
    }else{
        leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced);
        if(*unbalanced){
            if((*maxNode)->bf == -1){
                (*maxNode)->bf = 0;
                *unbalanced = FALSE;                
            }else if((*maxNode)->bf == 0){
                (*maxNode)->bf = 1;
                *unbalanced = FALSE;                
            }else  /* (*maxNode)->bf == 1 */ 
                leftRotation(maxNode, unbalanced);
        } 
    }
}

[此贴子已经被作者于2017-8-2 09:06编辑过]

//这种算法平衡因子的调整在删除函数中显得非常麻烦，avl树也比红黑树更难对付一些。
//上面的代码存在不少问题，这次努力做了修改，并把更完善一些的代码贴上，但恐怕某些地方还存在问题，实在没有精力去测试了。。。
//注释可能不够，等有空再补上

void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点！\n");
        return ;
    }
    if(strcmp(x.key, (*parent)->data.key) == 0){
        if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL))
        {    //情况1：无孩子 
            free(*parent);
            *parent = NULL;
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL))
        {    //情况2：无左孩子 
            temp = *parent;
            *parent = (*parent)->rightChild;
            free(temp);
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL))
        {    //情况3：无右孩子 
            temp = *parent;
            *parent = (*parent)->leftChild;
            free(temp);
             *unbalanced = TRUE;
        }else{    //情况4：有俩孩子 
            if((*parent)->leftChild->rightChild == NULL){//左孩无右孙 
                temp = *parent;
                *parent = (*parent)->leftChild;
                (*parent)->rightChild = temp->rightChild;
                free(temp);
                if((*parent)->bf == 0){
                    (*parent)->bf = -1;
                //    *unbalanced == FALSE;     未改变*unbalanced值
                }else if((*parent)->bf == 1){
                    (*parent)->bf = 0;
                     *unbalanced = TRUE;
                }else if((*parent)->bf == -1){
                    rightRotation(parent, unbalanced);
                    *unbalanced = TRUE; /* 旋转之后树变矮了，所以变得不平衡 */
                }
            }else{    //左孩有右孙 
        /* 只要左子树总体层高没变化，那么它返回去的时候就应当看作是平衡的 */
                int prebf = (*parent)->leftChild->bf;
                leftMaxNode(parent, &(*parent)->leftChild, unbalanced);
                if(prebf != 0 && prebf != (*parent)->leftChild->bf)
                    *unbalanced = TRUE;
                else
                    *unbalanced = FALSE;
                if(*unbalanced){
                    if((*parent)->bf == -1){
                        rightRotation(parent, unbalanced);
                    //    *unbalanced = TRUE;  未改变*unbalanced值
                    }else if((*parent)->bf == 0){
                        (*parent)->bf = -1;
                        *unbalanced = FALSE;
                    }else if((*parent)->bf == 1){
                        (*parent)->bf = 0;
                    //    *unbalanced = TRUE;     未改变*unbalanced值
                    } 
                }    
            }
        }
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlDelete(&(*parent)->leftChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == 1){
                (*parent)->bf = 0;
            //    *unbalanced = TRUE;   未改变*unbalanced值 
            }else if((*parent)->bf == 0){
                (*parent)->bf = -1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == -1){
                rightRotation(parent, unbalanced);
            //    *unbalanced = TRUE;         未改变*unbalanced值
            }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlDelete(&(*parent)->rightChild, x, unbalanced);
        if(*unbalanced)   
            if((*parent)->bf == -1){
                (*parent)->bf = 0;
            //    *unbalanced = TRUE;     未改变*unbalanced值
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            //    *unbalanced = TRUE;     未改变*unbalanced值
            }
    }
}

void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced)
{            /* 与左子树最大元交换，并删除结点 */
    if((*maxNode)->rightChild->rightChild == NULL){ 
        treePointer temp = *parent;
         
        *parent = (*maxNode)->rightChild;
        (*maxNode)->rightChild = (*maxNode)->rightChild->leftChild;
        (*parent)->leftChild = temp->leftChild;
        (*parent)->rightChild = temp->rightChild;
        (*parent)->bf = temp->bf;
        if((*maxNode)->bf == 0){
            (*maxNode)->bf = 1;
            *unbalanced = FALSE;     //未改变*unbalanced值
        }else if((*maxNode)->bf == -1){
            (*maxNode)->bf == 0;
            *unbalanced = TRUE;     
        }else if((*maxNode)->bf == 1){
            short int i = (*maxNode)->leftChild->bf;
            
            leftRotation(maxNode, unbalanced);
            if(i == 0){  //若子结点bf为0，说明有两个孩子，bf调整异于插入算法 
                (*maxNode)->bf = 1;
                (*maxNode)->leftChild->bf = 1;
            }
            (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
            preprintree(*maxNode);
        }   
        free(temp); 
        temp = NULL;/*还没搞懂，为什么只能放在最后free()*/ 
    }else{ 
        leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced);
        if(*unbalanced){
            if((*maxNode)->bf == -1){
                (*maxNode)->bf = 0;
            //    *unbalanced = TRUE;         未改变*unbalanced值        
            }else if((*maxNode)->bf == 0){
                (*maxNode)->bf = 1;
                *unbalanced = FALSE;                
            }else if((*maxNode)->bf == 1) 
                leftRotation(maxNode, unbalanced);
            //    *unbalanced = TRUE;  未改变*unbalanced值
                (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
        } 
    }
}