1123. Is It a Complete AVL Tree (30)[AVL樹+層序周遊]

1. 原題： https://www.patest.cn/contests/pat-a-practise/1123

2. 思路：

題意：

建構AVL, 層序輸出，再判斷該樹是否完全二叉樹。

思路：

題意不難，隻是有些麻煩。

根據AVL特點，先建樹，建構的時候進行平衡處理。之後用隊列輸出層序。

層序過程中，如果沒有周遊完結點，出現了空結點，那麼不是完全二叉樹。

已AC。

3. 源碼：

#include<iostream>
#include<algorithm>//使用max函數
#include<queue>
using namespace std;

struct Node
{
	Node() : left(NULL), right(NULL) {}//指針初始為空
	int data;
	Node *left, *right;
};
Node *T = NULL;//樹的根結點
int N;//總結點數

int getH(Node *T);//取得樹深度
Node *sinL(Node *T);//左單旋
Node *sinR(Node *T);//右單旋
Node *douLR(Node *T);//左右雙旋
Node *douRL(Node *T);//右左雙旋
Node *Insert(Node *T, int d);//插入建構AVL樹
void levelOrder();//層序周遊

int main()
{
	//freopen("in.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int d;
		cin >> d;
		T = Insert(T, d);
	}
	levelOrder();

	return 0;
}

int getH(Node *T)//取得樹深度
{
	if (T == NULL)
		return 0;
	else
		return(max(getH(T->left), getH(T->right)) + 1);//遞歸
}

Node *sinL(Node *T)//左單旋
{
	Node *A = T->right;
	T->right = A->left;
	A->left = T;
	return A;//新的根結點
}
Node *sinR(Node *T)//右單旋
{
	Node *A = T->left;
	T->left = A->right;
	A->right = T;
	return A;
}

Node *douLR(Node *T)//左右雙旋
{
	T->left = sinL(T->left);//先左旋
	T = sinR(T);//再右旋
	return T;
}

Node *douRL(Node *T)//右左雙旋
{
	T->right = sinR(T->right);
	T = sinL(T);
	return T;
}

Node *Insert(Node *T, int d)//遞歸插入建構AVL樹
{
	if (T == NULL)//遞歸結束條件
	{
		T = new Node;
		T->data = d;
	}
	else if (d < T->data)//插入左邊
	{
		T->left = Insert(T->left, d);
		if (getH(T->left) - getH(T->right) == 2)//平衡處理
		{
			if (d < T->left->data)
				T = sinR(T);
			else if (d > T->left->data)
				T = douLR(T);
		}
	}
	else if (d > T->data)//插入右邊
	{
		T->right = Insert(T->right, d);
		if (getH(T->right) - getH(T->left) == 2)
		{
			if (d < T->right->data)
				T = douRL(T);
			else if (d > T->right->data)
				T = sinL(T);
		}
	}

	return T;
}

void levelOrder()//層序輸出
{
	queue<Node *> Q;
	int flag = 1;//标記是否完全二叉樹
	Q.push(T);
	cout << T->data;
	int cnt = 1;//統計輸出的結點數

	while (!Q.empty())
	{
		Node *p = Q.front();
		Q.pop();

		if (p->left != NULL)
		{
			Q.push(p->left);
			cout << ' ' << p->left->data;
			cnt++;
		}
		else
		{
			if (cnt < N)//還沒周遊完結點，則不是完全二叉樹
				flag = 0;
		}

		if (p->right != NULL)
		{
			Q.push(p->right);
			cout << ' ' << p->right->data;
			cnt++;
		}
		else
		{
			if (cnt < N)
				flag = 0;
		}
	}

	if (flag == 1)
		cout << "\nYES\n";
	else
		cout << "\nNO\n";
}