AVL树的插入+层次遍历+判断是否为完全二叉树板子

#include
using namespace std;

const int N=100;
int l[N],r[N],v[N],h[N],idx;
int pos[N];
int p[N];
queue<int> q;
int root=0;
int n;
int update(int u){//更新深度
    h[u]=max(h[l[u]],h[r[u]])+1;
}

int R(int &u){//右旋
    int p=l[u];
    l[u]=r[p];
    r[p]=u;
    update(u),update(p);
    u=p;
}

int L(int &u){//左旋
    int p=r[u];
    r[u]=l[p];
    l[p]=u;
    update(u),update(p);
    u=p;
}

int get_balance(int u){//获取左子树-右子树高度差
    return h[l[u]]-h[r[u]];
}

void insert(int &u,int w){//在u节点处插入值为w的结点
    if(!u){
        u=++idx;
        v[u]=w;
    }else if(w<v[u]){
        //左
        insert(l[u],w);
        if(get_balance(u)==2){
            if(get_balance(l[u])==1){
                //右旋
                R(u);
            }else{
                L(l[u]);
                R(u);
            }
        }
    }else{
        //右
        insert(r[u],w);
        if(get_balance(u)==-2){
            if(get_balance(r[u])==-1){
                //左旋
                L(u);
            }else{
                R(r[u]);
                L(u);
            }
        }
    }
    update(u);
}

bool bfs(int root){//层次遍历 同时通过pos判断是否为完全二叉树
    pos[root]=1;
    q.push(root);
    int num=0;
    bool res=true;
    while(q.size()){
        int t=q.front();
        p[num++]=t;
        if(pos[t]>n)res=false;
        if(l[t]){
            pos[l[t]]=pos[t]*2;
            q.push(l[t]);
        }
        if(r[t]){
            pos[r[t]]=pos[t]*2+1;
            q.push(r[t]);
        }
        q.pop();
    }
    
    return res;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int w;
        cin>>w;
        insert(root,w);
    }
    
    int res=bfs(root);
    cout<<v[p[0]];
    for(int i=1;i<n;i++)cout<<" "<<v[p[i]];
    cout<<endl;
    
    if(res)cout<<"YES";
    else cout<<"NO";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106