C语言实现AVL均衡二叉树
1构造体
//这里定义一个取较大值的MAX宏#define MAX(a,b) ((a)>(b)?(a):(b))typedef struct AVLTreeNode { int data; //数据域 int height; //数据域 struct AVLTreeNode *left; //左子结点 struct AVLTreeNode *right; //右子结点} AVLTreeNode;2.1右单旋
/** * 右单旋 * 8 4 * 4 12 2 8 * 2 6 => 1 6 12 * 1 */AVLTreeNode *right_rotation(AVLTreeNode *root){ struct AVLTreeNode *new_root; new_root = root->left; root->left = new_root->right; new_root->right = root; //旋转完从新计算高度 root->height = MAX(Height(root->left) + 1, Height(root->right)); new_root->height = MAX(Height(new_root->left) + 1, Height(new_root->right)); return new_root;}2.2左单旋
/** * 左单旋 * 8 12 * 4 12 8 50 * 9 50 => 4 9 70 * 70 */AVLTreeNode *left_rotation(AVLTreeNode *root){ struct AVLTreeNode *new_root; new_root = root->right; root->right = new_root->left; new_root->left = root; //旋转完从新计算高度 root->height = MAX(Height(root->right) + 1, Height(root->left)); new_root->height = MAX(Height(new_root->right) + 1, Height(new_root->left)); return new_root;}2.3左右旋
/** * 左右旋 先对root->left左旋 再对root右旋 * 8 8 6 * 4 12 6 12 4 8 * 2 6 => 4 => 2 5 12 * 5 2 5 */AVLTreeNode *left_right_rotation(AVLTreeNode *root){ root->left = left_rotation(root->left); return right_rotation(root);}2.3右左旋
/** * 右左旋 先对root->right右旋 再对root左旋 * 8 8 10 * 4 12 4 10 8 12 * 10 14 => 9 12 => 4 9 14 * 9 14 */AVLTreeNode *right_left_rotation(AVLTreeNode *root){ root->right = right_rotation(root->right); return left_rotation(root);}3 自均衡
AVLTreeNode *rebalance(AVLTreeNode *root, int data){ if (Height(root->right) - Height(root->left) == 2) { if (data > root->right->data)//左单旋的状况 { printf("left_rotation \n"); root = left_rotation(root); }else{ printf("right_left_rotation \n");//右左旋的状况 root = right_left_rotation(root); } } if (Height(root->left) - Height(root->right) == 2) { if (data < root->left->data)//右单旋的状况 { printf("right_rotation \n"); root = right_rotation(root); }else{ printf("left_right_rotation \n");//左右旋的状况 root = left_right_rotation(root); } } return root;}4 插入
AVLTreeNode *insert(AVLTreeNode *root, int data){ if (NULL == root) { struct AVLTreeNode *node; node = (struct AVLTreeNode *)malloc(sizeof(struct AVLTreeNode)); if (node == NULL) { printf("malloc error \n"); return NULL; } node->data = data; node->right = NULL; node->left = NULL; return node; } if (data >= root->data) { root->right = insert(root->right, data); root->height = MAX(Height(root->left), Height(root->right) + 1);//相比于二叉搜寻树多了高度判断 }else{ root->left = insert(root->left, data); root->height = MAX(Height(root->left) + 1, Height(root->right)); } root = rebalance(root, data); return root;}5.1 查找最大/小节点
AVLTreeNode *FindMin(AVLTreeNode *root){ if (NULL == root) { return NULL; } if (root->left == NULL) { return root; }else{ return FindMin(root->left); }}AVLTreeNode *FindMax(AVLTreeNode *root){ if (NULL == root) { return NULL; } if (root->right == NULL) { return root; }else{ return FindMax(root->right); }}5.2删除
AVLTreeNode *Delete(AVLTreeNode *root, int target){ if (NULL == root) { return NULL; } if (target > root->data) { root->right = Delete(root->right, target); if (Height(root->left) - Height(root->right) == 2) { AVLTreeNode *l = root->left; if (Height(l->right) > Height(l->left)) root = left_right_rotation(root); else root = left_rotation(root); } }else if(target < root->data){ root->left = Delete(root->left, target); if (Height(root->right) - Height(root->left) == 2) { AVLTreeNode *r = root->right; if (Height(r->left) > Height(r->right)) root = left_right_rotation(root); else root = right_rotation(root); } }else{ //相等的状况 if (root->left && root->right) { if (Height(root->left) > Height(root->right)) { //左子树比右子树高 AVLTreeNode *max = FindMax(root->left); root->data = max->data; root->left = Delete(root->left, max->data); }else{ AVLTreeNode *min = FindMin(root->right); root->data = min->data; root->right = Delete(root->right, min->data); } }else{ struct AVLTreeNode *tmp; tmp = root; if (root->left == NULL) { root = root->right; }else if(root->right == NULL){ root = root->left; }else{ root = NULL;//删除本身 } } } return root;}测试：
int main(){ struct AVLTreeNode *node; node = NULL; node = insert(node, 8); node = insert(node, 4); node = insert(node, 12); node = insert(node, 10); node = insert(node, 14); node = insert(node, 9); printf("***前序***: \n"); preOrderTraverse(node); node = Delete(node, 10); printf("***前序***: \n"); preOrderTraverse(node);}