|
|
#include<stdio.h>
|
|
|
#include<stdlib.h>
|
|
|
|
|
|
typedef struct AVLNode* AVLTree;
|
|
|
struct AVLNode { //AVL树的结构：左子树，右子树，高度，数据
|
|
|
AVLTree Left;
|
|
|
AVLTree Right;
|
|
|
int Height;
|
|
|
int Data;
|
|
|
};
|
|
|
|
|
|
int Max(int a, int b) {
|
|
|
return a > b ? a : b;
|
|
|
}
|
|
|
|
|
|
int GetHeight(AVLTree T) { //递归计算树的高度
|
|
|
int HL, HR;
|
|
|
if (T) {
|
|
|
HL = GetHeight(T->Left);
|
|
|
HR = GetHeight(T->Right);
|
|
|
return Max(HL, HR) + 1;
|
|
|
}
|
|
|
else
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
|
|
|
AVLTree SingleLeftRotation(AVLTree A) {
|
|
|
AVLTree B = A->Left;
|
|
|
A->Left = B->Right;
|
|
|
B->Right = A;
|
|
|
A->Height = GetHeight(A);
|
|
|
B->Height = GetHeight(B);
|
|
|
return B;
|
|
|
}
|
|
|
|
|
|
AVLTree SingleRightRotation(AVLTree A) {
|
|
|
AVLTree B = A->Right;
|
|
|
A->Right = B->Left;
|
|
|
B->Left = A;
|
|
|
A->Height = GetHeight(A);
|
|
|
B->Height = GetHeight(B);
|
|
|
|
|
|
return B;
|
|
|
}
|
|
|
|
|
|
AVLTree DoubleLeftRightRotation(AVLTree A) {
|
|
|
A->Left = SingleRightRotation(A->Left);
|
|
|
return SingleLeftRotation(A);
|
|
|
}
|
|
|
|
|
|
AVLTree DoubleRightLeftRotation(AVLTree A) {
|
|
|
A->Right = SingleLeftRotation(A->Right);
|
|
|
return SingleRightRotation(A);
|
|
|
}
|
|
|
|
|
|
AVLTree Insert(AVLTree T, int x) {
|
|
|
if (!T) {
|
|
|
T = (AVLTree)malloc(sizeof(struct AVLNode));
|
|
|
T->Data = x;
|
|
|
T->Left = NULL;
|
|
|
T->Right = NULL;
|
|
|
T->Height = 1;
|
|
|
}
|
|
|
else if (x < T->Data) {
|
|
|
T->Left = Insert(T->Left, x);
|
|
|
if (GetHeight(T->Left) - GetHeight(T->Right) == 2) { //注意：这里还没更新树高，不能用T->Left->Height之类
|
|
|
if (x < T->Data)
|
|
|
T = SingleLeftRotation(T);
|
|
|
else if (x > T->Data)
|
|
|
T = DoubleLeftRightRotation(T);
|
|
|
}
|
|
|
}
|
|
|
else if (x > T->Data) {
|
|
|
T->Right=Insert(T->Right, x);
|
|
|
if (GetHeight(T->Left) - GetHeight(T->Right) == -2)
|
|
|
if (x > T->Right->Data)
|
|
|
T = SingleRightRotation(T);
|
|
|
else
|
|
|
T = DoubleRightLeftRotation(T);
|
|
|
}
|
|
|
T->Height = GetHeight(T);
|
|
|
return T;
|
|
|
}
|
|
|
|
|
|
void PreorderTravelsal(AVLTree BT) {
|
|
|
if (BT) {
|
|
|
printf("%d ", BT->Data);
|
|
|
PreorderTravelsal(BT->Left);
|
|
|
PreorderTravelsal(BT->Right);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main(void) {
|
|
|
int n,number, i;
|
|
|
AVLTree T = NULL;
|
|
|
scanf_s("%d", &n);
|
|
|
for (i = 0; i < n; i++) {
|
|
|
scanf_s("%d", &number);
|
|
|
T=Insert(T, number);
|
|
|
PreorderTravelsal(T);
|
|
|
printf("\n");
|
|
|
}
|
|
|
return 0;
|
|
|
} |
