pat1123 Is It a Complete AVL Tree,平衡二叉樹的建立，完全二叉樹判斷，層序

本題解決兩個問題，一個是建立平衡二叉樹，第二個數判斷此二叉樹是否為完全二叉樹。至于二叉樹的層序周遊，可以采用經典的方法，以隊列為輔助資料結構，層序輸出結點，并且正好可以在這一步裡來解決“完全二叉樹”的判定。

AVL Tree首先是一棵BST（Binary Search Tree），它的定義是遞歸的。除了滿足左子樹上的結點都小于根結點，右子樹上的結點都大于根結點之外，還應保證左右子樹的樹高之差的絕對值不能超過1。

具體定義可以參考《資料結構》課本，總體感覺AVL Tree是一棵特殊的BST，它的樹形更規範，比較對稱，不會出現“一頭沉”的狀況。

衆所周知，BST在二分查找的時候應用廣泛，但是如果BST的樹形很差，退化成隻有左子樹或右子樹，就變成單連結清單了，這時的查找就退化成線性的了。為了彌補這種殘缺，才出現了AVL Tree，AVL Tree可以保證不會出現那種退化的現象。

但是需要付出代價，就是樹形不好時，要做出調整，具體調整政策被概括為4種，LL，LR，RR，RL。

建立AVL Tree的主要函數是createAVL，函數的結尾調用adjustAVL來調整樹。

再說判斷Complete Binary Tree，隻需要在經典層序levelOrder的代碼裡面設定兩個bool型變量，emptyNode記錄第一個出現的空孩子，ret用來記錄空孩子後是否還有孩子。

本代碼亮點：

第一：node結點裡面定義level變量，将樹的高度資訊分散在結點裡，省去了getLevel遞歸調用對時間的消耗。屬于“以土地換和平”的政策，

第二：node結點定義了析構函數，在程式結尾釋放記憶體。可以采用crtdbg的方法來檢視記憶體是否洩漏。相關代碼在注釋行，需要在debug模式下運作。

#include<algorithm>
using std::max;
#include<queue>
using std::queue;
#include<vector>
using std::vector;
#include<stdio.h>

struct node{
	int val;
	node *lch = NULL, *rch = NULL;
	int level;
	node(int val_ = -1) :val(val_), level(1) {}
	~node() {
		if (lch) {
			delete lch;
			lch = NULL;
		}//if
		if (rch) {
			delete rch;
			rch = NULL;
		}//if
	}//~node
};//node
int getLevel(node*root) {
	return root == NULL ? 0 : root->level;
}//getLevel
node *LL(node*root) {
	node *ret = root->lch;
	root->lch = ret->rch;
	ret->rch = root;
	root->level = max(getLevel(root->lch), getLevel(root->rch)) + 1;
	ret->level = max(getLevel(ret->lch), getLevel(ret->rch)) + 1;
	return ret;
}//LL
node *RR(node*root) {
	node *ret = root->rch;
	root->rch = ret->lch;
	ret->lch = root;
	root->level = max(getLevel(root->lch), getLevel(root->rch)) + 1;
	ret->level = max(getLevel(ret->lch), getLevel(ret->rch)) + 1;
	return ret;
}//RR
node *LR(node*root) {
	node *child = root->lch;
	root->lch = RR(child);
	return  LL(root);
}//LR
node *RL(node*root) {
	node *child = root->rch;
	root->rch = LL(child);
	return RR(root);
}//RL
node* adjustAVL(node*root) {
	int diff = getLevel(root->lch) - getLevel(root->rch);
	if (diff >= -1 && diff <= 1)return root;
	int diff2(0);
		if (diff > 1) diff2 = getLevel(root->lch->lch) - getLevel(root->lch->rch);
		else if(diff < -1) diff2 = getLevel(root->rch->lch) - getLevel(root->rch->rch);
		if (diff == 2) {
			if (diff2 == 1)root = LL(root);
			else if(diff2 == -1) root = LR(root);
		}
		else if(diff == -2) {
		if (diff2 == -1)root = RR(root);
		else if(diff2 == 1) root = RL(root);
	}//if else if
	return root;
}//adjustOfAVL
node* createAVL(node*root, const int&tmpI) {
	if (root == NULL)root = new node(tmpI);
	else if(tmpI<root->val)root->lch = createAVL(root->lch, tmpI);
	else if(tmpI>root->val)root->rch = createAVL(root->rch, tmpI);
	root->level = max(getLevel(root->lch), getLevel(root->rch)) + 1;
	root = adjustAVL(root);
	return root;
}//createAVL
bool levelOrder(const node * const root, vector<int>&order) {
	queue<const node*> que;
	que.push(root);
	bool ret(true);
	bool emptyNode(false);
	while (que.empty() == false) {
		const node *cur = que.front();
		que.pop();
		order.push_back(cur->val);
		if (cur->lch) {
			que.push(cur->lch);
			if (emptyNode == true)ret = false;
		}
		else emptyNode = true;
		if (cur->rch) {
			que.push(cur->rch);
			if (emptyNode == true)ret = false;
		}
		else emptyNode = true;
	}//while
	return ret;
}//levelOrder
void printVec(const vector<int> &order) {
	int size = (int)order.size();
	for (int i(0); i < size - 1; ++i)printf("%d ", order[i]);
	printf("%d\n", order[size - 1]);
	return;
}//printVec

//#include<crtdbg.h>
//#defineCRTDBG_MAP_ALLOC
int main() {
	//_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF| _CRTDBG_LEAK_CHECK_DF);
#ifdef ONLINE_JUDGE
#else
	freopen("in.txt", "r", stdin);
#endif
	int N(-1);
	scanf("%d", &N);
	node *root(NULL);
	for (int i(0); i < N; ++i) {
		int tmpI(-1);
		scanf("%d", &tmpI);
		root = createAVL(root, tmpI);
	}//for i
	vector<int> order;
	bool flag = levelOrder(root, order);
	printVec(order);
	flag ? puts("YES") : puts("NO");
	if (root) {
		delete root;
		root = NULL;
	}//if
	return 0;
}//main
           

深入了解AVL Tree的調整政策，做了一個嘗試。

對于LR和RL，我用自己的實作，不需要借助LL和RR。

如果按照我下面這個實作，還需要更新三個結點的level。

結果和借助LR和RL的一樣。

但效率會比它高。

簡單分析一下就能明白，他們需要做4次結點level的更新，其中有一個結點被做了兩次。

我隻需要做3次更新。

細節：LR裡面的三個結點的更新順序一定root，tmpLch，ret。因為在新樹的結構下，ret的左孩子是tmpLch，右孩子是root，隻有孩子們先更新完了level，母親才能更新level。

順便一提，LL裡面的root和ret的更新順序，也是root在前，ret在後。

node *LR(node *root) {

   node *ret= root->lch->rch;

   node*tmpLch = root->lch;

   tmpLch->rch= ret->lch;

   root->lch= ret->rch;

   ret->rch= root;

   ret->lch= tmpLch;

   root->level= max(getLevel(root->lch), getLevel(root->rch)) + 1;

   tmpLch->level= max(getLevel(tmpLch->lch), getLevel(tmpLch->rch)) + 1;

   ret->level= max(getLevel(ret->lch), getLevel(ret->rch)) + 1;

   returnret;

}//LR

node *RL(node *root) {

   node *ret= root->rch->lch;

   node*tmpRch = root->rch;

   tmpRch->lch= ret->rch;

   root->rch= ret->lch;

   ret->lch= root;

   ret->rch= tmpRch;

   root->level= max(getLevel(root->rch), getLevel(root->lch)) + 1;

   tmpRch->level= max(getLevel(tmpRch->rch), getLevel(tmpRch->lch)) + 1;

   ret->level= max(getLevel(ret->rch), getLevel(ret->lch)) + 1;

   returnret;

}//RL

Gentle Dong,Second Version,20170224