浙大版《数据结构学习与实验指导(第2版)》进阶实验4-3.4:笛卡尔树

简介: 浙大版《数据结构学习与实验指导(第2版)》进阶实验4-3.4:笛卡尔树

题意:

Description

笛卡尔树是一种特殊的二叉树,其结点包含两个关键字K 1和K 2 。首先笛卡尔树是关于K 1 的二叉搜索树,即结点左子树的所有K 1 值都比该结点的K 1 值小,右子树则大。其次所有结点的K 2 关键字满足优先队列(不妨设为最小堆)的顺序要求,即该结点的K 2值比其子树中所有结点的K 2值小。给定一棵二叉树,请判断该树是否笛卡尔树。


Input

输入首先给出正整数N(≤ 1000),为树中结点的个数。随后N行,每行给出一个结点的信息,包括:结点的K 1值、K 2值、左孩子结点编号、右孩子结点编号。设结点从0 ∼ ( N − 1 ) 顺序编号。若某结点不存在孩子结点,则该位置给出−1。


Output

输出YES如果该树是一棵笛卡尔树;否则输出NO。

思路:

判断的重点在于:如何判断K1关键字的二叉搜索树,如果判断K2关键字的优先队列性质。

二叉搜索树的判断:中序遍历的K1序列是否为单调不递减序列

优先队列的判断:递归遍历的时候,判断子节点的K2值,是不是小于当前节点的K2值,以及,子节点是否满足此性质,递归判断就行了。

为了方便处理,把下标都加了1,这样就是从1开始了。

and 要先找到根节点,没有作为子节点的节点就是根节点,用map维护下就能找到。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
#define debug(x) cout<<#x<<":"<<x<<endl;
int n,order[maxn],idx=0;
struct node{
    int val1,val2;
    int lson,rson;
}a[maxn];
void dfs(int u){
    if(a[u].lson!=-1) dfs(a[u].lson);
    order[++idx]=a[u].val1;
    if(a[u].rson!=-1) dfs(a[u].rson);
}
bool isBST(int root){
    dfs(root);///中序遍历
    for(int i=1;i<n;i++)
        if(order[i]>order[i+1])
            return 0;
    return 1;
}
bool isHeap(int u){
    if(u==-1) return 1;
    if(a[u].lson!=-1){
        int t=a[u].lson;
        if(a[t].val2<a[u].val2) return 0;
        if(!isHeap(t)) return 0;
    }
    if(a[u].rson!=-1){
        int t=a[u].rson;
        if(a[t].val2<a[u].val2) return 0;
        if(!isHeap(t)) return 0;
    }
    return 1;
}
int main()
{
    map<int,int>mp;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].val1>>a[i].val2>>a[i].lson>>a[i].rson;
        if(a[i].lson!=-1) a[i].lson++,mp[a[i].lson]++;
        if(a[i].rson!=-1) a[i].rson++,mp[a[i].rson]++;
    }
    int root=1;///找到根节点
    while(mp.count(root)) root++;
    ///debug(root);
    if(isBST(root)&&isHeap(root)) puts("YES");
    else puts("NO");
    return 0;
}


目录
相关文章
|
15天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
24 1
|
15天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
26 0
|
18天前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
14 0
|
15天前
|
存储 NoSQL 安全
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
25 1
|
26天前
|
存储 算法
【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
|
7天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
29天前
数据结构 树(第10-14天)
数据结构 树(第10-14天)
|
12天前
|
存储
【数据结构】AVL树——平衡二叉搜索树
【数据结构】AVL树——平衡二叉搜索树
|
19天前
|
存储 算法
【C/数据结构与算法】:树和二叉树
【C/数据结构与算法】:树和二叉树
16 0
|
19天前
数据结构篇:旋转操作在AVL树中的实现过程
数据结构篇:旋转操作在AVL树中的实现过程
8 0