题意:
给你一个序列,让你插入到AVL树中,然后输出该AVL树的层序遍历,以及是否是一个完全二叉树。
题解:
涉及到AVL树插入时候的左旋、右旋操作,一共四种情况。
左子树的左子树插入结点(左左),左旋。
左子树的右子树插入结点(左右),先对左子树左旋,再对此节点右旋。
右子树的右子树插入结点(右右),右旋。
右子树的左子树插入结点(右左),先对右子树右旋,再对此节点左旋。
代码:
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stack>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e3+50;
const double eps = 1.e-8;
int n, a, flag = 0, complete = 1;
struct node {
int val;
node *left, *right;
};
node* leftRotate(node* root) {
node* temp = root->right;
root->right = temp->left;
temp->left = root;
return temp;
}
node* rightRotate(node* root) {
node* temp = root->left;
root->left = temp->right;
temp->right = root;
return temp;
}
node* leftRightRotate(node* root) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
node* rightLeftRotate(node* root) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
int getHeight(node* root) {
if (root == NULL) return 0;
int l = getHeight(root->left);
int r = getHeight(root->right);
return max(l,r)+1;
}
node* Insert(node* root, int val) {
if (root == NULL) {
root = new node();
root->val = val;
}
else if(val < root->val) {//left child
root->left = Insert(root->left, val);
int l = getHeight(root->left);
int r = getHeight(root->right);
if (l - r >= 2) {
if (root->left->val > val)
root = rightRotate(root);// a mistake, forget "root =".
else
root = leftRightRotate(root);
}
}
else {
root->right = Insert(root->right, val);
int l = getHeight(root->left);
int r = getHeight(root->right);
if (r - l >= 2) {
if (root->right->val < val)
root = leftRotate(root);
else
root = rightLeftRotate(root);
}
}
return root;
}
void levelOrder(node* root) {
vector<int> ans;
queue<node*> q;
q.push(root);
while(!q.empty()) {
node* t = q.front();
q.pop();
ans.push_back(t->val);
if (t->left != NULL) {
if (flag) complete = 0;
q.push(t->left);
}
else
flag = 1;
if (t->right != NULL) {
if (flag) complete = 0;
q.push(t->right);
}
else
flag = 1;
}
for (int i = 0; i < ans.size(); i++) {
printf("%d%c", ans[i], i == ans.size()-1 ? '\n' : ' ');
}
printf("%s\n", complete ? "YES" : "NO");
}
int main() {
cin>>n;
node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &a);
root = Insert(root, a);
}
levelOrder(root);
return 0;
}