)。
bistree_size
这是一个宏,用来计算二叉搜索树中结点的个数。直接访问BisTree结构体中的size成员即可。
/*bistree.c*/
#include <stdlib.h>
#include <string.h>
#include "bistree.h" /*bistree.h中包含bitree.h*/
static void destroy_right(BisTree *tree,BiTreeNode *node);
/* rotate_left 执行LL或LR旋转*/
static void rotate_left(BiTreeNode **node)
{
BiTreeNode *left, *grandchild;
/*设left为A的左子树*/
left = bitree_left(*node);
/*left结点的平衡因子为1,说明新插入的结点位于A的左子树的左子树上*/
if(((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY)
{
/*perform an LL rotation. 执行LL旋转*/
bitree_left(*node) = bitree_right(left); /*A的左指针指向left的右子结点*/
bitree_right(left) = *node; /*left的右指针指向A*/
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED; /*旋转后,将A的平衡因子改为0*/
((AvlNode *)bitree_date(left))-factor = AVL_BALANCED; /*旋转后,将left的平衡因子改为0*/
*node = left; /*将原来指向A的指针指向left*/
}
/*left结点的平衡因子不为1,说明插入的结点位于A的左子树的右子树上*/
else
{
/*perform an LR rotation. 执行LR旋转*/
grandchild = bitree_right(left); /*设grandchild为left的右子结点*/
bitree_right(left) = bitree_left(grandchild); /*将left的右子结点指向grch的左子结点*/
bitree_left(grandchild) = left; /*将grch的左子结点指向left*/
bitree_left(*node) = bitree_right(grandchild);/*将A的左子结点指向grch的右子结点*/
bitree_right(grandchild) = *node; /*grch的右子结点指向A*/
/*执行LR旋转后,调整结点的平衡因子取决于旋转前grch结点的原平衡因子值*/
switch(((AvlNode *)bitree_data(grandchild))->factor)
{
case AVL_LFT_HEAVY: /*如grch原平衡因子值为1,就将A的平衡因子设为-1,left的设为0*/
((AvlNOde *)bitree_data(*node))->factor = AVL_RGT_HEAVY;
((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;
break;
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;
&nbs