/*destroy_right 销毁右子树*/
static void destroy_right(BisTree *tree,BiTreeNode *node)
{
BiTreeNode **position;
/*如果树为空，直接返回*/
if(bitree_size(tree)==0)
return;
/*决定从何处销毁树*/
if(node==NULL) /*node未被指定时销毁整颗树*/
position=&tree->root;
else /*否则销毁指定结点的右子树*/
position=&node->right;
/*销毁子树*/
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*/
*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:
rotate_left(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node))->factor = AVL_LFT_HEAVY;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
break;
}
}
\*如果待插入结点的值大于当前结点的值*\
else if (cmpval>0)
{
/*向当前结点的右子树移动*/
/*如果当前结点的右子树不存在*/
if(bitree_is_eob(bitree_right(*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_right(tree,*node,avl_data)!=0)
return -1;
*balanced = 0;
}
/*如果当前结点的右子树不为空，递归调用insert向下插入*/
else
{
if(((retval = insert(tree,&bitree_right(*node),data,balanced))!=0)
return retval;
}
}
/*确定树仍然是保持平衡的*/
if(!(*balanced))
{
switch (((AvlNode *)bitree_data(*node))->factor)
{
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode*)bitree_data(*node))->factor = AVL_RGT_HEAVY;
break;
case AVL_RGT_HEAVY:
rotate_right(node);
*balanced=1;
}
}
}
/*待插入结点与当前结点(惰性隐藏)相等*/
else
{
if(!(AvlNode *)bitree_data(*node))->hidden)
{
return -1;
}
else
{
/*销毁当前结点中的数据*/
if(tree_destroy!=NULL)
{
tree->destroy(((AvlNode *)bitree_data(*node))->data);
}
/*将新数据插入到原来结点的位置上*/
((AvlNode *)bitree_data(*node))->data = (void *)data;
/*标识该结点不再为隐藏*/
((AvlNode *)bitree_data(*node))->hidden = 0;
/*这种情况下不需要再平衡树*/
*balanced = 1;
}
}
}
return 0;
}
/*hide 惰性移除*/
static int hide(BisTree *tree,BiTreeNode *node,const void *data)
{
int cmpval,retval;
if(bitree_is_eob(node))
{
/*数据没有被找到*/
return -1;
}
/*将待移除数据与当前结点数据相比较*/
cmpval = tree->compare(data,((AvlNode*)bitree_data(node))->data);
if(cmpval < 0)
{
/*向左移动*/
retval = hide(tree,bitree_left(node),data);
}
else if(cmpval > 0)
{
/*向右移动*/
retval = hide(tree,bitree_right(node),data);
}
else
{
/*两个数据相等，将结点隐藏*/
((AvlNode *)bitree_data(node))->hidden = 1;
retval = 0;
}
return retval;
}
/*lookup 查找二叉树中的结点*/
static int lookup(BisTree *tree,BiTreeNode *node,void **data)
{
int cmpval,retval;
if(bitree_is_eob(node))
{
/*数据结点没有找到*/
return -1;
}
cmpval = tree->compare(*data,((AvlNode *)bitree_data(node))->data);
if(cmpval < 0)
{
/*向左移动,递归查询*/
retval = lookup(tree,bitree_left(node),data);
}
else if(cmpval > 0)
{
/*向右移动，递归查询*/
retval = lookup(tree,bitree_right(node),data);
}
else
{
if(!(AvlNode *)bitree_data(node))->hidden)
{
/*找到结点且未被隐藏，从树中返回该结点数据*/
*data = ((AvlNode *)bitree_data(node))->data);
return 0;
}
else
{
/*如已隐藏，返回数据未被找到*/
return -1;
}
}
return retval;
}
/*bistree_init 初始化二叉搜索树*/
void bistree_init(BisTree *tree,int(*compare)(const void *key1,const void *key2),void (*destroy)(void *data))
{
bitree_init(tree,destroy);
tree->compare=compare;
return;
}
/*bistree_destroy 销毁二叉搜索树*/
void bistree_destroy(BisTree *tree)
{
/*Destroy all nodes in the tree.*/
destroy_left(tree,NULL);
/*No operations are allowed now,but clear the structure as a precaution.*/
memset(tree,0,sizeof(BisTree));
return;
}
/*bistree_insert 向二叉树中插入结点*/
int bistree_insert(BisTree *tree,const void *data)
{
int balanced=0;
return insert{tree,&bitree_root(tree),data,&balanced);
}
/*bistree_remove 惰性移除*/
int bistree_remove(BisTree *tree,const void *data)
{
return hide(tree,bitree_root(tree),data);
}