D:失败
**实现描述:
**注意事项:
** >> 在此其实并不会删除dnode, 而是将rnode的值给了dnode, 再删了rnode.
** 因为在此使用的递归算法, 如果真把dnode给释放了，会造成压栈的信息出现错误!
**作 者: # Qifeng.zou # 2013.12.19 #
******************************************************************************/
int avl_replace_and_delete(avl_tree_t *tree, avl_node_t *dnode, avl_node_t *rnode, bool *lower)
{
avl_node_t *parent = NULL, *rparent = NULL;
if(NULL == rnode->rchild)
{
*lower = true;
parent = dnode->parent;
rparent = rnode->parent;
dnode->key = rnode->key; /* 注: 将rnode的值给了dnode */
if(rnode == dnode->lchild)
{
avl_set_lchild(dnode, rnode->lchild);
/* rnode->parent == dnode节点可能失衡，此处理交给前栈的函数处理 */
}
else
{
avl_set_rchild(rparent, rnode->lchild);
/* rnode的父节点可能失衡，此处理交给前栈的函数处理 */
}
free(rnode), rnode=NULL; /* 注意: 释放的不是dnode, 而是rnode */
return AVL_SUCCESS;
}
avl_replace_and_delete(tree, dnode, rnode->rchild, lower);
if(true == *lower)
{
/* dnode的父节点可能失衡，此处理交给前栈的函数处理
但dnode可能使用，因此必须在此自己处理 */
avl_delete_right_balance(tree, rnode, lower);
}
return AVL_SUCCESS;
}
代码3 替换并删除节点（内部接口）
/******************************************************************************
**函数名称: avl_delete_left_balance
**功 能: 节点node的左子树某节点被删除, 左高度降低后, 平衡化处理(内部接口)
**输入参数:
** tree: 平衡二叉树
** node: 节点node的左子树的某个节点已被删除
**输出参数:
** lower: 高度是否变化
**返 回: AVL_SUCCESS:成功 AVL_FAILED:失败
**实现描述:
**注意事项:
**作 者: # Qifeng.zou # 2013.12.19 #
******************************************************************************/
int avl_delete_left_balance(avl_tree_t *tree, avl_node_t *node, bool *lower)
{
avl_node_t *rchild = NULL, *rlchild = NULL, *parent = node->parent;
switch(node->bf)
{
case LH: /* 左高: 左子树高度减1 树变矮 */
{
node->bf = EH;
*lower = true;
break;
}
case EH: /* 等高: 左子树高度减1 树高度不变 */
{
node->bf = RH;
*lower = false;
break;
}
case RH: /* 右高: 左子树高度减1 树失去平衡 */
{
rchild = node->rchild;
switch(rchild->bf)
{
case EH: /* RR型: 向左旋转 */
case RH: /* RR型: 向左旋转 */
{
if(EH == rchild->bf)
{
*lower = false;
rchild->bf = LH;
node->bf = RH;
}
else if(RH == rchild->bf)
{
*lower = true;
rchild->bf = EH;
node->bf = EH;
}
avl_set_rchild(node, rchild->lchild);
avl_set_lchild(rchild, node);
avl_replace_child(tree, parent, node, rchild);
break;
}
case LH: /* RL型: 先向右旋转 再向左旋转 */
{
*lower = true;
rlchild = rchild->lchild;
switch(rlchild->bf)
{
case LH:
{
node->bf = EH;
rchild->bf = RH;
rlchild->bf = EH;
break;
}
case EH:
{
node->bf = EH;
rchild->bf = EH;
rlchild->bf = EH;
break;
}
case RH:
{
node->bf = LH;
rchild->bf = EH;
rlchild->bf = EH;
break;
}
}
avl_set_rchild(node, rlchild->lchild);
avl_set_lchild(rchild, rlchild->rchild);
avl_set_lchild(rlchild, node);
avl_set_rchild(rlchild, rchild);
avl_replace_child(tree, parent, node, rlchild);
break;
}
}
break;
}
}
return AVL_SUCCESS;
}
代码4 左子树高度降低后平衡化处理
/******************************************************************************
**函数名称: avl_delete_right_balance
**功 能: 节点node的右子树某节点被删除, 左高度降低后, 平衡化处理(内部接口)
**输入参数:
** tree: 平衡二叉树
** node: 节点node的右子树的某个节点已被删除
**输出参数:
** lower: 高度是否变化
**返 回: AVL_SUCCESS:成功 AVL_FAILED:失败
**实现描述:
**注意事项:
**作 者: # Qifeng.zou # 2013.12.19 #
******************************************************************************/
int avl_delete_right_balance(avl_tree_t *tree, avl_node_t *node, bool *lower)
{
avl_node_t *lchild = NULL, *lrchild = NULL, *pa