IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> PAT甲级 1123 判断完全 AVL 树 -> 正文阅读

[数据结构与算法]PAT甲级 1123 判断完全 AVL 树

原题链接

AVL树是一种自平衡二叉搜索树。

在AVL树中,任何节点的两个子树的高度最多相差 1 个。

如果某个时间,某节点的两个子树之间的高度差超过 1,则将通过树旋转进行重新平衡以恢复此属性。

图 1?4 说明了旋转规则。

?

现在,给定插入序列,请你输出得到的AVL树的层序遍历,并判断它是否是完全二叉树。

输入格式
第一行包含整数 N,表示插入序列中元素个数。

第二行包含 N 个不同的整数表示插入序列。

输出格式
第一行输出得到的AVL树的层序遍历序列。

第二行,如果该AVL树是完全二叉树,则输出 YES,否则输出 NO。

数据范围
1≤N≤20
输入样例1:
5
88 70 61 63 65
输出样例1:
70 63 88 61 65
YES
输入样例2:
8
88 70 61 96 120 90 65 68
输出样例2:
88 65 96 61 70 90 120 68
NO

我的解法:

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int l[N], r[N], h[N], idx;
int v[N], q[N], pos[N];
int n;
int get_balance(int u){
    return h[l[u]] - h[r[u]];
}
void update(int u){
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}
void R(int &u){
    int p = l[u];
    l[u] = r[p];
    r[p] = u;
    update(u);
    update(p);
    u = p;
}
void L(int &u){
    int p = r[u];
    r[u] = l[p];
    l[p] = u;
    update(u);
    update(p);
    u = p;
}
void insert(int &u, int 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){
    q[0] = root;
    pos[root] = 1; // 对应到完全二叉树中的1节点,pos用来判断是否是完全二叉树,我们可以先假设它是
    bool res = true;
    int hh = 0, tt = 0;
    while(hh <= tt){
        int t = q[hh ++]; // 出队
        if(pos[t] > n) res = false;
        if(l[t]) q[++tt] = l[t], pos[l[t]] = 2*pos[t];  // 出队
        if(r[t]) q[++tt] = r[t], pos[r[t]] = 2*pos[t] + 1; // 出队
        
    }
    return res;
}
int main(){
    cin >> n;
    int root = 0;
    for(int i = 0; i < n; i ++ ){
        int w;
        cin >> w;
        insert(root, w);
    }
    bool res = bfs(root);
    for(int i = 0; i < n; i ++ ){
        cout << v[q[i]] << " ";
    }
    puts("");
    if(res) puts("YES");
    else puts("NO");
    return 0;
}

收获:

avl的操作看似复杂,其实很好背,熟练记忆后考场上直接默写

判断一棵树是不是完全二叉树,可以先假设这是一颗完全二叉树,然后层序遍历该二叉树,在遍历的过程中,引入pos[]来记录每个节点的位置,根据pos[ l[ t ] ] = pos[ t ]*2,pos[ r[ t ] ] = pos[ t ] * 2 + 1的性质给pos赋值,如果出现比n(节点数)要大的pos值,则证明假设不成立,该树不是一颗完全二叉树

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-26 15:23:34  更:2022-05-26 15:24:08 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/1 0:38:05-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码