PAT - 甲级 - 1123. Is It a Complete AVL Tree (30)

题目描述：

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

    

    

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print "YES" if the tree is complete, or "NO" if not.

5
88 70 61 63 65

70 63 88 61 65
YES

8
88 70 61 96 120 90 65 68

88 65 96 61 70 90 120 68
NO

题目思路：

单纯的平衡二叉排序树，只要根据图片写出左旋和右旋即可。需要增加的功能是判断是否是完全二叉树，如何判断是否该树是否是完全二叉树树呢，有一种比较渐变的判断方法。按照层次遍历的方式给该二叉树编号，如果编号和满二叉树的编号一样，那么该树就是完全二叉树。

题目代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// tree 
struct Avl{int v, height;int order;Avl *lchild, *rchild;
};
// 构造 
Avl *newAvl(int v){Avl *avl = new Avl;avl->v = v;avl->height = 1;avl->lchild = avl->rchild = NULL;return avl;
}
// 获取高度 
int getHeight(Avl *root){if(root == NULL) return 0;return root->height;
}
// 获得平衡因子 
int getBalanceFactor(Avl *root){return getHeight(root->lchild) - getHeight(root->rchild);
}
// 更新高度 
void updateHeight(Avl *root){root->height = max(getHeight(root->lchild), getHeight(root->rchild))+1;
}
// 左旋 
void L(Avl *&root){Avl *temp = root->rchild;root->rchild = temp->lchild;temp->lchild = root;updateHeight(root);updateHeight(temp);root = temp;
}
// 右旋 
void R(Avl *&root){Avl *temp = root->lchild;root->lchild = temp->rchild;temp->rchild = root;updateHeight(root);updateHeight(temp);	root = temp;
}// 插入数据 
void insert(Avl *&root, int v){if(root == NULL){root = newAvl(v);return ;}if(v < root->v){insert(root->lchild, v);updateHeight(root);if(getBalanceFactor(root) == 2){if(getBalanceFactor(root->lchild) == 1){ //LLR(root);}else if(getBalanceFactor(root->lchild) == -1){ // LRL(root->lchild);R(root); }} }else{insert(root->rchild, v);updateHeight(root);if(getBalanceFactor(root) == -2){if(getBalanceFactor(root->rchild) == -1){ // RRL(root);}else if(getBalanceFactor(root->rchild) == 1){ // RLR(root->rchild);L(root);}}}}
// 建AVL树 
Avl *Creat(int data[], int n){Avl *root = NULL;for(int i = 0; i < n; i++){insert(root, data[i]);}return root;
}
// 存放层次遍历的结果 
vector<Avl*> level;
// bfs求层次遍历 
void levelorder(Avl* root){Avl* p = root;root->order = 1; // 利用各个结点在树中位置的编号的数学关系计算 queue<Avl*>q;q.push(p);while(!q.empty()){p = q.front();level.push_back(p);if(p->lchild != NULL){q.push(p->lchild);p->lchild->order = 2 * p->order;} if(p->rchild != NULL){q.push(p->rchild);p->rchild->order = 2 * p->order + 1;}q.pop();}
}int main(){int n;scanf("%d",&n);int data[n];for(int i = 0; i < n; i++){scanf("%d",&data[i]);}Avl* root = Creat(data, n);levelorder(root); for(int i = 0; i < n; i++){if(i != 0) printf(" ");printf("%d",level[i]->v);}puts("");if(level[n-1]->order != n){puts("NO");}else{puts("YES");}return 0;
}