PAT甲组1066.Root of AVL Tree

2020-03-02

A1066

个人思路

构造平衡二叉树解题。最开始在新建节点Node* newNode(int v){}函数，忘记写返回值了，一直再报段错误，寻思着也没有数组，咋回越界呢，废了半天劲才找到错误。

AC代码

#include <bits/stdc++.h>
using namespace std;
int N;
struct Node{
	int data, height;
	Node* lchild;
	Node* rchild;
};
Node* newNode(int v)
{
	Node* node = new Node;
	node->data = v;
	node->height = 1;
	node->lchild = node->rchild = NULL;
	return node;
}
int getHeight(Node* root)
{
	if(root == NULL)
		return 0;
	return root->height;
}
int getBF(Node* root)
{
	return getHeight(root->lchild) - getHeight(root->rchild);
}
void update(Node* root)
{
	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void R_rotation(Node* &root)
{
	Node* temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	update(root);
	update(temp);
	root = temp;
}
void L_rotation(Node* &root)
{
	Node* temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	update(root);
	update(temp);
	root = temp;
}
void insert(Node* &root, int v)
{
	if(root == NULL)
	{
		root = newNode(v);
		return; 
	}
	if(v < root->data)
	{
		insert(root->lchild, v);
		update(root);
		if(getBF(root) == 2)
		{
			if(getBF(root->lchild) == 1)
			{
				R_rotation(root);
			}
			else if(getBF(root->lchild) == -1)
			{
				L_rotation(root->lchild);
				R_rotation(root);
			}
		}
	}
	else
	{
		insert(root->rchild, v);
		update(root);
		if(getBF(root) == -2)
		{
			if(getBF(root->rchild) == -1)
			{
				L_rotation(root);
			}
			else if(getBF(root->rchild) == 1)
			{
				R_rotation(root->rchild);
				L_rotation(root);
			}
		}
	}
}
int main(int argc, char *argv[]) {
	scanf("%d", &N);
	Node* root = NULL;
	for(int i = 0; i < N; ++i)
	{
		int num;
		scanf("%d", &num);
		insert(root, num);
	}
	printf("%d", root->data);
	return 0;
}

另附平衡二叉树基本操作详解代码

BST：二叉搜索树，AVL：平衡二叉树

#include <bits/stdc++.h>
using namespace std;
int LL[10] = {7, 5, 8, 3, 6, 2, 4},
	LR[10] = {7, 3, 8, 2, 5, 4, 6},
	RR[10] = {3, 5, 2, 4, 7, 6, 8},
	RL[10] = {3, 2, 7, 5, 8, 4, 6},
	AVL[10] = {5, 3, 7, 2, 4, 6, 8};
struct Node{
	int data;
	int height;
	int level = 1;
	Node* lchild;
	Node* rchild;
};
Node* newNode(int v)
{
	Node* node = new Node;
	node->data = v;
	node->height = 1;//默认高度为1
	node->lchild = node->rchild = NULL;  
	return node;
}
void levelOrder(Node* root)
{
	queue<Node*> q;
	//root->level = 1;
	q.push(root);
	while(!q.empty())
	{
		Node* now = q.front();
		q.pop();
		printf("(%d,%d) ", now->data, now->level);
		if(now->lchild != NULL)
		{
			now->lchild->level = now->level + 1;
			q.push(now->lchild);
		}
		if(now->rchild != NULL)
		{
			now->rchild->level = now->level + 1;
			q.push(now->rchild);
		}
	}
	cout << endl;
}
int getHeight(Node* root)//获取当前节点高度 :其中涉及空节点高度为0的情况 
{
	if(root == NULL)//节点为空 
		return 0;
	return root->height;
} 
int getBalanceFactor(Node* root)//获取当前节点的平衡因子 
{
	return getHeight(root->lchild) - getHeight(root->rchild);//root节点左子树的高度-右子树的高度 
}
void updateHeight(Node* root)//更新当前节点的高度 
{
	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void leftRotation(Node* &root)
{
	Node* temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	//更新节点高度
	updateHeight(root);
	updateHeight(temp);
	root = temp; 
}
void rightRotation(Node* &root)
{
	Node* temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	//更新节点高度
	updateHeight(root);
	updateHeight(temp);
	root = temp; 
}
void AVLinsert(Node* &root, int v)
{
	if(root == NULL)//到达空节点，查找失败，即是插入位置 
	{
		root = newNode(v);
		return;
	}
	if(v < root->data)//比根节点小，往左子树走 
	{
		AVLinsert(root->lchild, v);
		updateHeight(root);//每次插入后要更新树高
		if(getBalanceFactor(root) == 2)//属于L型 
		{
			cout << "出现不平衡" << endl;
			if(getBalanceFactor(root->lchild) == 1)//LL型
			{
				cout << "LL型" << endl;
				rightRotation(root);
			}
			else if(getBalanceFactor(root->lchild) == -1)//LR型
			{
				cout << "LR型" << endl;
				leftRotation(root->lchild);
				rightRotation(root);
			} 
		} 
		else
			cout << "插入正常" << endl;
	}
	else//大于等于根节点，往右子树走 
	{
		AVLinsert(root->rchild, v);
		updateHeight(root);
		if(getBalanceFactor(root) == -2)//属于R型
		{
			cout << "出现不平衡" << endl;
			if(getBalanceFactor(root->rchild) == -1)//RR型 
			{
				cout << "RR型" << endl;
				leftRotation(root); 
			} 
			else if(getBalanceFactor(root->rchild) == 1)//RL型 
			{
				cout << "RL型" << endl;
				rightRotation(root->rchild);
				leftRotation(root);
			}
		} 
		else
		{ 
			cout << "插入正常" << endl; 
		} 
	}
}
void BSTinsert(Node* &root, int v)
{
	if(root == NULL)
	{
		root = newNode(v);
		return;
	}
	if(v < root->data)
		BSTinsert(root->lchild, v);
	else
		BSTinsert(root->rchild, v);
} 
int main(int argc, char *argv[]) {
	Node* BSTroot = NULL;
	Node* AVLroot = NULL;
	for(int i = 0; i < 7; ++i)
	{
		BSTinsert(BSTroot, RR[i]);
	}
	levelOrder(BSTroot);
	for(int i = 0; i < 7; ++i)
	{
		AVLinsert(AVLroot, RR[i]);
	}
	levelOrder(AVLroot);
	return 0;
}