1123. Is It a Complete AVL Tree.md

pat 甲级 1123 Is It a Complete AVL Tree

题意概述

向 AVL 树插入多个关键字，给出最终得到的 AVL 树的层次遍历序列并判断它是否为完全二叉树。

输入输出格式

输入第一行都包含一个正整数 N，它是要插入的关键字的总数。然后在下一行中给出 N 个不同的整数键。一行中的所有数字都用空格分隔。

第一行打印给出最终得到的 AVL 树的层次遍历序列。第二行判断它是否为完全二叉树，如果是，输出YES；否则输出NO。

数据规模

$$N<=20$$

算法设计

AVL 树的代码模板可见AVL 树代码模板

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
//与根结点数据域相等时，一律插入到右子树
struct AVLTreeNode {
    gg data, height, num;  //关键字、高度
    AVLTreeNode *left, *right;
    AVLTreeNode(gg v, AVLTreeNode* l = nullptr, AVLTreeNode* r = nullptr,
                gg h = 0) :
        data(v),
        height(h), left(l), right(r) {}
};
gg getHeight(AVLTreeNode* r) { return r ? r->height : 0; }
AVLTreeNode* findAVL(AVLTreeNode* root, gg data) {
    if (not root or root->data == data) {
        return root;
    } else if (data < root->data) {
        return findAVL(root->left, data);
    } else {
        return findAVL(root->right, data);
    }
}
// LL：左左对应的情况(左单旋转),返回旋转后的根节点
AVLTreeNode* leftLeftRotation(AVLTreeNode* k2) {
    AVLTreeNode* k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(getHeight(k2->left), getHeight(k2->right)) + 1;
    k1->height = max(getHeight(k1->left), k2->height) + 1;
    return k1;
}
// RR：右右对应的情况(右单旋转),返回旋转后的根节点
AVLTreeNode* rightRightRotation(AVLTreeNode* k1) {
    AVLTreeNode* k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(getHeight(k1->left), getHeight(k1->right)) + 1;
    k2->height = max(getHeight(k2->right), k1->height) + 1;
    return k2;
}
// LR：左右对应的情况(左双旋转),返回旋转后的根节点
AVLTreeNode* leftRightRotation(AVLTreeNode* k3) {
    k3->left = rightRightRotation(k3->left);
    return leftLeftRotation(k3);
}
// RL：右左对应的情况(右双旋转),返回旋转后的根节点
AVLTreeNode* rightLeftRotation(AVLTreeNode* k1) {
    k1->right = leftLeftRotation(k1->right);
    return rightRightRotation(k1);
}
//将结点插入到AVL树中，并返回根节点
AVLTreeNode* insertNode(AVLTreeNode*& root, gg data) {
    if (not root) {
        root = new AVLTreeNode(data);
    } else if (data < root->data) {
        root->left = insertNode(root->left, data);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节。
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            if (data < root->left->data) {
                root = leftLeftRotation(root);
            } else {
                root = leftRightRotation(root);
            }
        }
    } else {  // 应该将data插入到"root的右子树"的情况
        root->right = insertNode(root->right, data);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节。
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            if (data > root->right->data) {
                root = rightRightRotation(root);
            } else {
                root = rightLeftRotation(root);
            }
        }
    }
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}
void bfs(AVLTreeNode* root, gg ni) {
    queue<pair<AVLTreeNode*, gg>> q;  // pair的second成员存储结点编号
    q.push({root, 1});
    bool ans = true;
    for (gg i = 1; not q.empty(); ++i) {
        auto t = q.front();
        cout << t.first->data << (i == ni ? "\n" : " ");
        q.pop();
        if (i != t.second)
            ans = false;
        if (t.first->left)
            q.push({t.first->left, t.second * 2});
        if (t.first->right)
            q.push({t.first->right, t.second * 2 + 1});
    }
    cout << (ans ? "YES" : "NO");
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ai;
    cin >> ni;
    AVLTreeNode* root = nullptr;
    for (gg i = 0; i < ni; ++i) {
        cin >> ai;
        root = insertNode(root, ai);
    }
    bfs(root, ni);
    return 0;
}