详解二叉搜索树的实现源码(3)

case AVL_BALANCED: /*如grch原平衡因子值为0，就将A的平衡因子设为0，left的设为0*/
            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
            break;

case AVL_RGT_HEAVY: /*如grch原平衡因子值为-1，就将A的平衡因子设为0，left的设为1*/
            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;
            break;
        }
        /*在所有情况下，grch的新平��因子都为0*/
        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        /*将原来指向A的指针指向grch.*/
        *node = grandchild;
    }
    return;
}
/*rotate_right 执行LR旋转*/
static void rotate_right(BiTreeNode **node)
{
    BiTreeNode *right, *grandchild;
    /*设right为A的右子树*/
    right=bitree_right(*node);
    /*判断right的平衡因子，-1代表新节点位于A的右子树的右子树上*/
    if(((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY)
    {
        /*perform an RR rotation. 执行RR旋转*/
        bitree_right(*node)=bitree_left(right);                /*将A的右子结点指向right的左子结点*/
        bitree_right(right)=*node;                              /*将right的左子结点指向A*/
        ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED; /*将A的平衡因子设为0*/
        ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED; /*将right的平衡因子设为0*/
        *node = right;                                          /*原来指向A的指针指向right*/
    }
    else
    {
        /*perform an RL rotation. 执行RL旋转*/
        grandchild = bitree_left(right);                /*设grch为right的左孩子*/
        bitree_left(right) = bitree_right(grandchild);  /*将right的左子结点指向grch的右子结点*/
        bitree_right(grandchild) = right;              /*将grch的右子结点指向right*/
        bitree_right(*node)=bitree_left(grandchild);    /*将A的右子结点指向grch的左子结点*/
        bitree_left(grandchild) = *node;                /*将grch的左子结点指向A*/
        /*执行RL旋转后，调整结点的平衡因子取决于旋转前grch的原平衡因子*/
        switch(((AvlNode *)bitree_data(grandchild))->factor)
        {
        case AVL_LFT_HEAVY:/*如grch原平衡因子值为1，就将A的平衡因子设为0，right的设为-1*/
            ((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
            ((AvlNode *)bitree_data(*right))->factor = AVL_RGT_HEAVY;
            break;

case AVL_BALANCED:/*如grch原平衡因子值为0，就将A的平衡因子设为0，right的设为0*/
            ((AvlNode *)bitree_data(*node))->facotr = AVL_BALANCED;
            ((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;
            break;
        case AVL_RGT_HEAVY:/*如grch原平衡因子值为-1，就将A的平衡因子设为1，right的设为0*/
            ((AvlNode *)bitree_data(*node))->facotr = AVL_LFT_BALANCED;
            ((AvlNode *)bitree_data(right))->facotr = AVL_BALANCED;
            break;
        }
        /*在所有情况下，grch的新平衡因子都为0*/
        ((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;
        /*将原来指向A的指针指向grch*/
        *node = grandchild;
    }
    return;
}
/*destroy_left 销毁左子树*/
static void destroy_left(BisTree *tree,BiTreeNode *node)
{
    BiTreeNode **position;
   
    /*如果树为空，直接返回*/
    if(bitree_size(tree)==0)
        return;
    /*决定从何处销毁子树*/
    if(node==NULL) /*node未指定，销毁整棵树*/
        position = &tree->root;
    else          /*否则销毁指定结点的左子树*/
        position = &node->left;
    /*销毁子树*/
    if(*position != NULL)
    {
        destroy_left(tree,*position);  /*递归调用*/
        destroy_right(tree,*position);
       
        if(tree->destroy != NULL)
        {
            /*调用用户定义函数来释放动态分配的数据*/
            tree->destroy(((AvlNode *)(*position)->data)->data);
        }
        /*释放AVL数据节点，并释放node结点本身*/
        free((*position)->data);
        free(*position);
        *position = NULL;
       
        /*调整树的大小*/
        tree->size--;
    }
    return;
}