pbixy2zje/AVL树.cpp

#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;
}