單詞

complete binary tree 完全二叉樹

restore 修復 恢復

題目

1628848464776.png

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.

Sample Input 1:

5
88 70 61 63 65
結(jié)尾無空行

Sample Output 1:

70 63 88 61 65
YES
結(jié)尾無空行

Sample Input 2:

8
88 70 61 96 120 90 65 68
結(jié)尾無空行

Sample Output 2:

88 65 96 61 70 90 120 68
NO
結(jié)尾無空行

思路

平衡二叉樹的題目模板固定艘希。

判斷一個樹是否為完全二叉樹祭刚，層次遍歷，若出現(xiàn)空節(jié)點后又出現(xiàn)了節(jié)點，則不是完全二叉樹旬盯。

代碼

#include <bits/stdc++.h>
using namespace std;

vector<int> ans;
int flag = 1;
int after = 0;

struct node{
    int v, height;
    node *lchild, *rchild;
    node(int data): v(data), height(1), lchild(NULL), rchild(NULL){
    }
};

int getHeight(node* root) {
    if (root == NULL) return 0;
    return root->height;
}

void updateHeight(node* root) {
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

int getFactor(node* root) {
    return getHeight(root->lchild) - getHeight(root->rchild);
}

void L(node* &root) {
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void R(node* &root) {
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void insert(node* &root, int v) {
    if (root == NULL) {
        root = new node(v);
        return;
    }
    if (v < root->v) {
        insert(root->lchild, v);
        updateHeight(root);
        if (getFactor(root) == 2) {
            if (getFactor(root->lchild) == 1) {
                R(root);
            } else if(getFactor(root->lchild) == -1) {
                L(root->lchild);
                R(root);
            }
        }
    } else {
        insert(root->rchild, v);
        updateHeight(root);
        if (getFactor(root) == -2) {
            if (getFactor(root->rchild) == 1) {
                R(root->rchild);
                L(root);
            } else if(getFactor(root->rchild) == -1) {
                L(root);
            
            }
        }
    }
}

void level(node *root) {
    if (root == NULL) {
        flag = 2;
        return;
    }
    queue<node*> mq;
    mq.push(root);
    while (!mq.empty()) {
        node* now = mq.front();
        ans.push_back(now->v);
        mq.pop();
        if (flag == 1) {
            if (now->lchild != NULL || now->rchild != NULL) flag = 2;
        }
        if (now->lchild != NULL) {
            if (after) flag = 0;
            mq.push(now->lchild);
        } else {
            after = 1;
        }
        if (now->rchild != NULL) {
            if (after) flag = 0;
            mq.push(now->rchild);
        } else {
            after = 1;
        }
        
        
    }
}


int main() {
    int n;
    int data[10000];
    cin>>n;
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        cin>>data[i];
        insert(root, data[i]);
    }
    level(root);
    for (int i = 0; i < n; i++) {
        cout<<ans[i];
        if (i != n - 1) cout<<" ";
        else cout<<endl;
    }
    
    if (flag == 0) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    
}