PAT.1123 Is It a Complete AVL Tree - AVL树

题目给出插入顺序，要求根据插入顺序构建AVL树，并给出AVL树的层序遍历并判断其是否为完全二叉树。

一边听网课一遍做这道题，一开始想着避免在建树的时候反复搜索高度，于是把树高写成了节点的属性，结果庸人自扰，导致在旋转时涉及了高度更新的代码，浪费了一些时间去想，而且很容易出错。

然后是莫名其妙地，一开始自己在设计节点数据结构的时候做了一个指向父节点的指针，虽然实际求解过程中完全用不到，但是还是像个伞兵一样在旋转的时候写了这个指针的更新策略。

一些尝试

综上两点，写代码的时候出现了大量屎山，虽然最后程序确实能通过样例，但是测试点234仍然不过，于是得分20/30。

#include

using namespace std;
typedef long long ll;

struct node{
    int val;
    int f;
    node* l;
    node* r;
    node* parent;
    void init(int val){
        this->val = val;
        this->f = 1;
        this->l = nullptr;
        this->r = nullptr;
        this->parent = nullptr;
    }
};

bool isComplete = true,isLastNonLeafAppear = false;
int nodeCnt,tVal;
node* root;
queue<node*> treeLevel;

//左旋
void rotateL(node* subRoot){
    node *rl = subRoot->r->l;
    //先更新f值
    subRoot->f = max((rl == nullptr ? 0 : rl->f),(subRoot->l == nullptr ? 0 : subRoot->l->f)) + 1;
    subRoot->r->f = max((subRoot->r->r == nullptr ? 0 : subRoot->r->r->f),subRoot->f) + 1;

    //subroot parent相关
    subRoot->r->parent = subRoot->parent;
    if(subRoot->parent == nullptr) root = subRoot->r;
    else if(subRoot->parent->l == subRoot) subRoot->parent->l = subRoot->r;
    else if(subRoot->parent->r == subRoot) subRoot->parent->r = subRoot->r;

    subRoot->parent = subRoot->r;
    subRoot->r->l = subRoot;
    subRoot->r = rl;
    if(rl != nullptr) rl->parent = subRoot;
}

//右旋
void rotateR(node* subRoot){
    node *lr = subRoot->l->r;
    //先更新f值
    subRoot->f = max((lr == nullptr ? 0 : lr->f),(subRoot->r == nullptr ? 0 : subRoot->r->f)) + 1;
    subRoot->l->f = max((subRoot->l->l == nullptr ? 0 : subRoot->l->l->f),subRoot->f) + 1;

    //subroot parent相关
    subRoot->l->parent = subRoot->parent;
    if(subRoot->parent == nullptr) root = subRoot->l;
    else if(subRoot->parent->l == subRoot) subRoot->parent->l = subRoot->l;
    else if(subRoot->parent->r == subRoot) subRoot->parent->r = subRoot->l;

    subRoot->parent = subRoot->l;
    subRoot->l->r = subRoot;
    subRoot->l = lr;
    if(lr != nullptr) lr->parent = subRoot;
}

void AVLbalance(node* subRoot,string type){
    type = type.substr(0,2);
    if(type == "LL"){
        rotateR(subRoot);
    }else if(type == "RR"){
        rotateL(subRoot);
    }else if(type == "LR"){
        rotateL(subRoot->l);
        rotateR(subRoot);
    }else if(type == "RL"){
        rotateR(subRoot->r);
        rotateL(subRoot);
    }
}

void AVLinsert(int val){
    node* insertNode = (node*)malloc(sizeof(node));
    insertNode->init(val);
    if(root == nullptr){
        root = insertNode;
        return;
    }
    node *cNode = root,*preNode = nullptr,*imbalanceRoot = nullptr;
    string insertFlag = "L",imbalanceType = "";
    while(cNode != nullptr){
        cNode->f++;
        if(preNode != nullptr && cNode == preNode->l){
            if(abs(cNode->f - (preNode->r == nullptr ? 0 : preNode->r->f)) > 1){
                imbalanceRoot = preNode;
                imbalanceType = "L";
            }
        }else if(preNode != nullptr && cNode == preNode->r){
            if(abs((preNode->l == nullptr ? 0 : preNode->l->f) - cNode->f) > 1){
                imbalanceRoot = preNode;
                imbalanceType = "R";
            }
        }
        preNode = cNode;
        if(val > cNode->val){
            insertFlag = "R";
            cNode = cNode->r;
        }else if(val < cNode->val){
            insertFlag = "L";
            cNode = cNode->l;
        }
        if(imbalanceRoot != nullptr) imbalanceType += insertFlag;
    }
    
    if(insertFlag == "R") preNode->r = insertNode;
    else if(insertFlag == "L") preNode->l = insertNode;
    insertNode->parent = preNode;
    
    if(imbalanceRoot != nullptr) AVLbalance(imbalanceRoot,imbalanceType);
}

int main(){
    cin>>nodeCnt;
    for(int i = 0 ; i < nodeCnt ; ++i){
        cin>>tVal;
        AVLinsert(tVal);
    }
    //完全二叉树的检查，不存在只有右孩子的节点，只有左孩子的节点或叶子结点出现后只能出现叶子节点
    treeLevel.push(root);
    while(!treeLevel.empty()){
        node* cNode = treeLevel.front();
        cout<<cNode->val;
        treeLevel.pop();
        if(cNode->l != nullptr){
            if(isLastNonLeafAppear) isComplete = false;
            treeLevel.push(cNode->l);
            if(cNode->r == nullptr) isLastNonLeafAppear = true;
        }
        if(cNode->r != nullptr){
            if(isLastNonLeafAppear) isComplete = false;
            treeLevel.push(cNode->r);
            if(cNode->l == nullptr) isComplete = false;
        }
        if(cNode->l == nullptr && cNode->r == nullptr) isLastNonLeafAppear = true;
        if(treeLevel.size() != 0) cout<<' ';
    }
    cout<<endl<<(isComplete ? "YES" : "NO")<<endl;
}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

题解

整理了思路然后重新写了一遍：

不用变量维护树的高度是要付出代价的————每次判断节点是否失衡都要搜索当前节点左右子树的深度，虽然用递归也很好实现。

递归建树也是要付出代价的————每次插入节点都会更新插入路径上所有的连接关系，虽然这道题最多只有20个节点。

那就这样吧，每次插入节点都用递归自底向上更新一遍节点的连接关系，在更新的同时搜索当前节点左右子树的深度，如果当前节点失衡就对当前节点为根的树进行旋转，然后将新的根节点返回，以供给高层节点建立连接。

这样操作每次插入节点，最外层的递归函数返回的总是整棵树的根，所以不断插入、不断记录根节点即可。

最后判断完全二叉树，因为建树的时候用了链式结构，这里不能直接用顺序存储下标判断的方法，所以要么层序遍历树，将链式关系存储到线性空间，然后用下标判断，要么想想完全二叉树的特点，然后用一定的规律来判断。

大概想了一下是这样的：

完全二叉树中不存在只有右孩子的节点
在层序遍历的过程中，一旦出现只有左孩子的节点或者叶子节点后，后续的节点必须都是叶子结点

然后用这两个条件判断一下就完事儿了。

#include

using namespace std;
typedef long long ll;

struct node{
    int val;
    node* l;
    node* r;
    node(){
        l = r = nullptr;
    }
    node(int t){
        val = t;
        l = r = nullptr;
    }
};

bool isComplete = true,isLastNonLeafAppear = false;
int nodeCnt,tVal;
node* root;
queue<node*> treeLevel;

int getTreeDepth(node* cNode){
    if(cNode == nullptr) return 0;
    return max(getTreeDepth(cNode->l),getTreeDepth(cNode->r)) + 1;
}

//左旋
node* rotateL(node* subRoot){
    node* t = subRoot->r;
    subRoot->r = t->l;
    t->l = subRoot;
    return t;
}

//右旋
node* rotateR(node* subRoot){
    node* t = subRoot->l;
    subRoot->l = t->r;
    t->r = subRoot;
    return t;
}

//递归建立AVL，返回当前节点以供上一层建立连接
node* build(int val,node* cNode){
    if(cNode == nullptr){
        cNode = new node(val);
        return cNode;
    }
    if(val > cNode->val){
        cNode->r = build(val,cNode->r);
        if(abs(getTreeDepth(cNode->l) - getTreeDepth(cNode->r)) > 1){
            if(val > cNode->r->val){
                //RR
                cNode = rotateL(cNode);
            }else if(val < cNode->r->val){
                //RL
                cNode->r = rotateR(cNode->r);
                cNode = rotateL(cNode);
            }
        }
    }else if(val < cNode->val){
        cNode->l = build(val,cNode->l);
        if(abs(getTreeDepth(cNode->l) - getTreeDepth(cNode->r)) > 1){
            if(val < cNode->l->val){
                //LL
                cNode = rotateR(cNode);
            }else if(val > cNode->l->val){
                //LR
                cNode->l = rotateL(cNode->l);
                cNode = rotateR(cNode);
            }
        }
    }
    return cNode;
}

int main(){
    cin>>nodeCnt;
    for(int i = 0 ; i < nodeCnt ; ++i){
        cin>>tVal;
        root = build(tVal,root);
    }
    treeLevel.push(root);
    while(!treeLevel.empty()){
        node* cNode = treeLevel.front();
        cout<<cNode->val;
        treeLevel.pop();
        if(cNode->l != nullptr){
            if(isLastNonLeafAppear) isComplete = false;
            treeLevel.push(cNode->l);
            if(cNode->r == nullptr) isLastNonLeafAppear = true;
        }
        if(cNode->r != nullptr){
            if(isLastNonLeafAppear) isComplete = false;
            treeLevel.push(cNode->r);
            if(cNode->l == nullptr) isComplete = false;
        }
        if(cNode->l == nullptr && cNode->r == nullptr) isLastNonLeafAppear = true;
        if(treeLevel.size() != 0) cout<<' ';
    }
    cout<<endl<<(isComplete ? "YES" : "NO")<<endl;
}

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

相关阅读:
实验29：循迹传感器实验
 Ubuntu20.24安装记录——安装VM-Tools
ARM器件和DSP器件的区别
 The AFFiNE live demo is here (with 15 reasons from the team why you should try)
Oracle技术分享 ORA-01145异常
 Geom2d_TrimmedCurve解析
 JavaScript中的数值
 数学建模学习（104）：线性回归和多元回归【补充版】
ArcGIS api for JavaScript 制作统计专题图
 Microsemi Libero SoC 教程1 (Libero开发环境)
原文地址：https://blog.csdn.net/weixin_43662405/article/details/126729388