平衡二叉树c语言版

一、定义二叉树结点结构体

/*** 定义平衡二叉树结点
*/
struct avlbinarytree
{    //数据域NodeData*  data;///树高int  h;struct avlbinarytree*  left;struct avlbinarytree*  right;
};
typedef struct avlbinarytree AVLNode;

二、声明函数的操作

/*** 创建结点
*/
AVLNode* create_avlbinarytree_node(NodeData* data);/**** 计算树高度
*/
int   get_avltree_h(AVLNode* childRoot);/*** 添加结点
*/
void  insert_avlbinarytree_node(AVLNode** tree,NodeData*  data);/*** 平衡操作
*/
void  do_avltree_roate(AVLNode** root);/*** 前序遍历
*/
void  per_order_avlbinarytree(AVLNode* root);/*** LL型，左孩子的左子树添加删除引起的失衡*         5                                       3*       .   .           平衡操作                .     .*      3     6      -------------->            2     5 *     .  .                                    .    .    .*    2    4                                  1     4     6*   .*  1* * 平衡操作：左子树整体右旋，将根节点左孩子提到根节点，原根结点变成新根节点的右孩子,新根结点的原右孩子变成原根节点的左孩子*
*/
void  ll_roate_avl(AVLNode** root);/*** RR型右孩子的右子树添加删除引起的失衡*          2                               4*       .     .                         .     .*       1     4      ------->           2     6  *          .    .                     .   .  .    *          3    6                     1   3  5*             .  *             5*
*/void  rr_roate_avl(AVLNode** root);
/*** LR型，左孩子的右子树添加删除引起的失衡*         5                    5                           3*       .   .               .     .                     .     .*      2     6              3     6                     2     5 *     .  .       ------> .   .          ------->      .     .    .*         .            .*          4          1*平衡操作：左子树先做一次RR左旋，再做一次LL右旋
*/
void  lr_roate_avl(AVLNode** root);/*** RL型右孩子的左子树添加删除引起的失衡*          2                        2                                4*       .     .                   .    .                           .     .*       1     5    ------->      1     4       ---->               2       5*          .    .                    .    .                      .    .      .*          4    6                   3      5                    1      3      6*         .                                  .*        3                                     6*        *平衡操作： 先将右子树做一次LL右旋，在做一次RR左旋
*/
void  rl_roate_avl(AVLNode** root);

三、平衡二叉树操作函数定义

/*** 创建结点*/
AVLNode *create_avlbinarytree_node(NodeData *data)
{AVLNode *node = malloc(sizeof(AVLNode *));if (node == NULL){perror("创建AVLNode结点失败");return NULL;}node->data = malloc(sizeof(NodeData *));if (node->data == NULL){perror("AVLNode数据域分配内存空间失败");return NULL;}*(node->data) = *data;node->h = 1;node->left = NULL;node->right = NULL;return node;
}
/*** 获取树高*/
int get_avltree_h(AVLNode *childRoot)
{if (childRoot == NULL){return 0;}int l = get_avltree_h(childRoot->left) + 1;int r = get_avltree_h(childRoot->right) + 1;return l > r ? l : r;
}void insert_avlbinarytree_node(AVLNode **tree, NodeData *data)
{if (*tree == NULL){AVLNode *newNode = create_avlbinarytree_node(data);*tree = newNode;return;}/// 左子树if (*data < *((*tree)->data)){insert_avlbinarytree_node(&((*tree)->left), data);}//右子树if (*data > *((*tree)->data)){insert_avlbinarytree_node(&((*tree)->right), data);}
}void  do_avltree_roate(AVLNode** root)
{int lh = get_avltree_h((*root)->left);int rh = get_avltree_h((*root)->right);/// 左子树高于右子树造成的不平衡if(lh-rh>1){int llh =  get_avltree_h((*root)->left->left);int lrh =  get_avltree_h((*root)->left->right);bool isLL = llh > lrh ;if(isLL)ll_roate_avl(root);elselr_roate_avl(root);}/// 右子树高于左子树造成的不平衡if(rh-lh>1){int rlh =  get_avltree_h((*root)->right->left);int rrh =  get_avltree_h((*root)->right->right);bool isRR = rrh > rlh ;if(isRR)rr_roate_avl(root);elserl_roate_avl(root);      }
}void per_order_avlbinarytree(AVLNode *root)
{if (root == NULL){return;}printf("d-avlbinarytree:  %d\n", *(root->data));per_order_avlbinarytree(root->left);per_order_avlbinarytree(root->right);
}void ll_roate_avl(AVLNode **root)
{printf("lr_roate_avl----LL型\n");//  (*root)->left = temp->right;//  temp->right = (*root);//  *root = temp; AVLNode *temp =(*root)->left->right;(*root)->left->right = *root;*root =(*root)->left;(*root)->right->left= temp;
}void rr_roate_avl(AVLNode **root)
{printf("lr_roate_avl----RR型\n");AVLNode *temp = (*root)->right->left;(*root)->right->left = *root;*root = (*root)->right;(*root)->left->right = temp;
}void lr_roate_avl(AVLNode **root)
{printf("lr_roate_avl----LR型\n");AVLNode *leftTree = (*root)->left;rr_roate_avl(&leftTree);(*root)->left = leftTree;ll_roate_avl(root);
}void rl_roate_avl(AVLNode **root)
{printf("lr_roate_avl----RL型\n");AVLNode *rightRoot = (*root)->right;ll_roate_avl(&rightRoot);(*root)->right = rightRoot;rr_roate_avl(root);
}

四、平衡二叉树测试

void   test_avlbinarytree()
{//RR型  {1,2,3,4,5,6};//LL型  {7,6,5,4,3,2,1};//LR型  {5,2,6,1,3,4};//RL型  {4,3,8,6,5,10};NodeData  arr[] = {4,3,8,6,5,10};int len = sizeof(arr)/sizeof(arr[0]);int i;AVLNode* root = NULL;for(i=0;i<len;i++){insert_avlbinarytree_node(&root,&arr[i]);do_avltree_roate(&root);}printf("start 中序遍历---\n");per_order_avlbinarytree(root);int lh = get_avltree_h(root->left);int rh = get_avltree_h(root->right);printf("树高度lh= %d, rh= %d\n",lh,rh);}