#include<stdio.h>
#include<stdlib.h>
typedef struct avlnode *position;
typedef struct avlnode *avltree;
struct avlnode {
int num;
avltree left;
avltree right;
int height;
};
int height(position p) {
if (p == NULL) {
return -1;
}
else {
return p->height;
}
}
int max(position t1, position t2) {
return height(t1) > height(t2) ? height(t1) : height(t2);
}
position singlerotatewithleft(avltree k2) {
position k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(k2->left, k2->right) + 1;
k1->height = max(k2, k1->left) + 1;
return k1;//k1 is the new root
}
position singlerotatewithright(avltree k2) {
position k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = max(k2->left, k2->right) + 1;
k1->height = max(k2, k1->right) + 1;
return k1;//k1 is the new root
}
//下面的左儿子的右子树双旋转函数只能在k3节点有左儿子并且k3的左儿子有右子树的时候调用,用来解决k3的左儿子的右子树太长引起的问题，这种旋转叫做左右双旋转，left-right double rotation，事实上是对k3->left进行了一次右单旋转，之后再对k3进行一次左单旋转，之后的另一个右左双旋转就是它的镜面版本
position doublerotatewithleft(position k3) {
k3->left = singlerotatewithright(k3->left);
k3 = singlerotatewithleft(k3);
return k3;
}
position doublerotatewithright(position k3) {
k3->right = singlerotatewithleft(k3->right);
k3 = singlerotatewithright(k3);
return k3;
}
avltree insert(int x, avltree t) {
if (t == NULL) {
t = (avltree)malloc(sizeof(struct avlnode));
t->num = x;
t->left = NULL;
t->right = NULL;
t->height = 0;
}
else if (x < t->num) {
t->left = insert(x, t->left);
if (height(t->left) - height(t->right) == 2) {//当height(t->left) - height(t->right) == 2时，不可能出现x==t->left->num
if (x < t->left->num) {
t = singlerotatewithleft(t);
}
else {
t = doublerotatewithleft(t);
}
}
}
else if (x > t->num) {
t->right = insert(x, t->right);
if (height(t->right) - height(t->left) == 2) {
if (x > t->right->num) {
t = singlerotatewithright(t);
}
else {
t = doublerotatewithright(t);
}
}
}
t->height = (height(t->left) > height(t->right) ? height(t -> left) : height(t->right)) + 1;
return t;
}
void preorder(avltree t) {
if (t != NULL) {
printf("data=%d height=%d\n", t->num,t->height);
preorder(t->left);
preorder(t->right);
}
}
int main() {
avltree t = NULL;
int a;
while (1) {
printf("输入新数据:\n");
scanf("%d", &a);
t = insert(a, t);
preorder(t);
}
return 0;
}
D3m0nF
发布了4 篇原创文章 · 获赞 0 · 访问量 51
私信
关注