|
bsp; /*重置*position*/
*position = NULL;
/*调整树的大小*/
tree->size--;
}
return;
}
/*insert 插入操作*/
static int insert(BisTree *tree,BiTreeNode **node,const void *data,int *balanced)
{
AvlNode *avl_data;
int cmpval,retval;
/*将数据插入到树中*/
/*如果*node是分支的结束,即*node=NULL*/
if(bitree_is_eob(*node))
{
/*操作插入到空树中，设置结点的AVL属性值*/
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode)))==NULL)
return -1;
avl_data->factor = AVL_BALANCED;
avl_data->hidden = 0;
avl_data->data = (void *)data;
/*将数据插入为根结点*/
return bitree_ins_left(tree,*node,avl_data);
}
else
{
/*控制插入到非空树中 将待插入数据与当前结点的数据相比较*/
cmpval = tree->compare(data,((AvlNode *)bitree_data(*node))->data);
/*待插入结点的数据小于当前结点的数据*/
if(cmpval < 0)
{
/*向当前结点的左子树移动*/
/*如果当前结点的左子树不存在*/
if(bitree_is_eob(bitree_left(*node)))
{
if((avl_data = (AvlNode *)malloc(sizeof(AvlNode)))==NULL）
return -1;
/*将待插入结点插入到当前结点左侧，并设置AVL属性值*/
avl_data->factor=AVL_BALANCED;
avl_data->hidden=0;
avl_data->data=(void *)data;
if(bitree_ins_left(tree,*node,avl_data)!=0)
return -1;
*balanced=0;
}
/*如果当前结点的左子树不为空，递归调用insert向下插入*/
else
{
if((retval = insert(tree,&bitree_left(*node),data,balanced))!=0)
retrun retval;
}
}
/*确保树仍保持平衡*/
if(!(*balanced))
{
switch(((AvlNode *)bitree_data(*node))->factor)
{
case AVL_LFT_HEAVY:
&n |