一、定义二叉树结点结构体
/*** 定义平衡二叉树结点
*/
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);}
