这个AVL有问题吗
  • 板块P2073 送花
  • 楼主LuBoqi
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/15 18:45
  • 上次更新2023/10/28 06:32:04
查看原帖
这个AVL有问题吗
588587
LuBoqi楼主2022/3/15 18:45

要改去世了啊啊啊

#include <iostream>
using namespace std;
struct Node {			//AVL树结构体
	int W;
	int C;
	int height;
	struct Node* Right;
	struct Node* Left;
};
typedef struct Node Flower;
typedef struct Node* Flowers;			//方便书写,简洁化

static int Beauty, Price;			//统计结果

int Max(int n, int m) {				//max函数
	if (n > m) {
		return n;
	}
	else {
		return m;
	}
}

int High(Flowers T) {			//获取节点高度
	if (T == NULL) {
		return -1;
	}
	else {
		return T->height;
	}
}

Flowers SingleRotateWithLeft(Flowers T) {			//左单旋转
	Flowers H;
	H = T->Left;
	T->Left = H->Right;
	H->Right = T;
	T->height = Max(High(T->Left), High(T->Right)) + 1;
	H->height = Max(High(H->Left), High(H->Right)) + 1;
	return H;
}

Flowers SingleRotateWithRight(Flowers T) {			//右单旋转
	Flowers H;
	H = T->Right;
	T->Right = H->Left;
	H->Left = T;
	T->height = Max(High(T->Left), High(T->Right)) + 1;
	H->height = Max(High(H->Left), High(H->Right)) + 1;
	return H;
}

Flowers DoubleRotateWithRight(Flowers T) {			//右双旋转
	T->Right = SingleRotateWithLeft(T->Right);
	return SingleRotateWithRight(T);
}

Flowers DoubleRotateWithLeft(Flowers T) {			//左双旋转
	T->Left = SingleRotateWithRight(T->Left);
	return SingleRotateWithLeft(T);
}

Flowers Insert(Flowers T, int w, int c) {			//插入结点
	if (T == NULL) {			//递归终点
		T = new Flower();
		T->C = c;
		T->W = w;
		T->Right = T->Left = NULL;
	}
	else if (c < T->C) {
		T->Left = Insert(T->Left, w, c);			//左递归插入
		if (High(T->Left) - High(T->Right) == 2) {		//是否需要旋转调整
			if (c < T->Left->C) {
				T = SingleRotateWithLeft(T);
			}
			else {
				T = DoubleRotateWithLeft(T);
			}
		}
	}
	else if (c > T->C) {
		T->Right = Insert(T->Right, w, c);			//右递归插入
		if (High(T->Right) - High(T->Left) == 2) {			//是否需要旋转调整
			if (c > T->Right->C) {
				T = SingleRotateWithRight(T);
			}
			else {
				T = DoubleRotateWithRight(T);
			}
		}
	}

	T->height = Max(High(T->Left), High(T->Right)) + 1;			//高度赋值
	return T;
}

Flowers DeleteMax(Flowers T) {			//递归删除树中C最大结点
	if (T->Right == NULL) {			//递归终点
		Flowers H = T->Left;
		delete T;
		return H;
	}
	else {
		T->Right = DeleteMax(T->Right);
		T->height = Max(High(T->Left), High(T->Right)) + 1;

		if (High(T->Left) - High(T->Right) == 2) {			//判断删除后是否需要旋转
			if (High(T->Left->Left) >= High(T->Left->Right)) {			//单旋转
				T = SingleRotateWithLeft(T);
			}
			else if (High(T->Left->Left) < High(T->Left->Right)) {			//双旋转
				T = DoubleRotateWithLeft(T);
			}
		}
		T->height = Max(High(T->Left), High(T->Right)) + 1;
		return T;
	}
}

Flowers DeleteMin(Flowers T) {			//递归删除树中C最小结点
	if (T->Left == NULL) {			//递归终点
		Flowers H = T->Right;
		delete T;
		return H;
	}
	else {
		T->Left = DeleteMax(T->Left);

		if (High(T->Right) - High(T->Left) == 2) {			//判断是否需要旋转
			if (High(T->Right->Right) >= High(T->Right->Left)) {			//单旋转
				T = SingleRotateWithRight(T);
			}
			else if (High(T->Right->Right) < High(T->Right->Left)) {			//双旋转
				T = DoubleRotateWithRight(T);
			}
		}
		T->height = Max(High(T->Left), High(T->Right)) + 1;
		return T;
	}
}

void Statistics(Flowers T) {			//递归统计结果
	if (T == NULL) {			//递归终点
		return;
	}
	else {
		Beauty += T->W;
		Price += T->C;
		Statistics(T->Left);
		Statistics(T->Right);
	}
}

//void show(Flowers T) {
//	if (T == NULL) {
//		return;
//	}
//	cout << "W:" << T->W << " C:" << T->C << endl;
//	show(T->Left);
//	show(T->Right);
//}

int main() {
	int operation, w, c;
	Flowers T = NULL;
	while (true) {
		cin >> operation;
		if (T == NULL && operation != 1) {
			continue;
		}
		switch (operation) {			//多路开关操作数
		case 1: {
			cin >> w >> c;
			T = Insert(T, w, c);
			break;
		}case 3: {
			T = DeleteMax(T);
			break;
		}case 2: {
			T = DeleteMin(T);
			break;
		}case -1: {
			Statistics(T);
			//show(T);
			cout << Beauty << " " << Price << endl;
			return 0;
		}
		}
	}
}

2022/3/15 18:45
加载中...