[C++知识库]PAT Root of AVL Tree(C++实现)

题目链接7-6 Root of AVL Tree (25 分)

运行结果

我的代码

#include<iostream>
using namespace std;

//返回较大值
int Max(int a, int b)
{
	return a > b ? a : b;
}

//结点
struct Node {
	int Data;
	Node * Left;
	Node * Right;
	int Height;
};
using Position = Node * ;


class AVLTree
{
public:
	AVLTree();
	~AVLTree();
	Position& GetRoot();
	const int GetHeight(const Position& TreeNode);
	void Insert(Position& Root, const int X);
	//左单旋
	Position SingleLeftRotation(Position A);
	//右单旋
	Position SingleRightRotation(Position A);
	//左右双旋
	Position DoubleLeftRightRotation(Position A);
	//右左双旋
	Position DoubleRightLeftRotation(Position A);
	//销毁
	void Destroy(Position& Root);
private:
	Position Root;
};

AVLTree::AVLTree() : Root { nullptr } {}

AVLTree::~AVLTree()
{
	Destroy(Root);
}

//返回根结点的引用
Position& AVLTree::GetRoot() { return Root; }

//求以某个结点为根节点的树高
const int AVLTree::GetHeight(const Position& TreeNode)
{
	if (!TreeNode)
		return 0;
	return Max(GetHeight(TreeNode->Left), GetHeight(TreeNode->Right)) + 1;
}


void AVLTree::Insert(Position& Root, const int X)
{
	if (!Root) {
		Root = new Node;
		Root->Data = X;
		Root->Height = 1;
		Root->Left = Root->Right = nullptr;
	}
	else if (X < Root->Data) {
		Insert(Root->Left, X);
		if (GetHeight(Root->Left) - GetHeight(Root->Right) == 2)
			if (X < Root->Left->Data)
				//左单旋
				Root = SingleLeftRotation(Root);
			else
				//左右双旋
				Root = DoubleLeftRightRotation(Root);
	}
	else if (X > Root->Data) {
		Insert(Root->Right, X);
		if (GetHeight(Root->Right) - GetHeight(Root->Left) == 2)
			if (X > Root->Right->Data)
				//右单旋
				Root = SingleRightRotation(Root);
			else
				//右左双旋
				Root = DoubleRightLeftRotation(Root);
	}
	Root->Height = Max(GetHeight(Root->Left), GetHeight(Root->Right)) + 1;
}

//左单旋
Position AVLTree::SingleLeftRotation(Position A)
{
	Position B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
	B->Height = Max(GetHeight(B->Left), A->Height) + 1;
	return B;
}

//右单旋
Position AVLTree::SingleRightRotation(Position A)
{
	Position B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
	B->Height = Max(GetHeight(B->Right), A->Height) + 1;
	return B;
}

//左右双旋
Position AVLTree::DoubleLeftRightRotation(Position A)
{
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}

//右左双旋
Position AVLTree::DoubleRightLeftRotation(Position A)
{
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

void AVLTree::Destroy(Position& Root)
{
	if (!Root)
		return;
	Destroy(Root->Left);
	Destroy(Root->Right);
	delete Root;
	Root = nullptr;
}


int main()
{
	int N, X;
	cin >> N;
	AVLTree T{};
	for (int i = 0; i < N; ++i) {
		cin >> X;
		T.Insert(T.GetRoot(), X);
	}
	cout << T.GetRoot()->Data;
}