P2171 Hz吐泡泡
题目背景
Hz大大是一种可爱的动物(神)。他很喜欢吐泡泡(更喜欢写作业)。
题目描述
这天,Hz大大心血来潮,吐了n个不同的泡泡玩(保证没有重复的泡泡)。因为他还要写作业,所以他请你帮他把这些泡泡排序成树(左子树<=根<右子树)。输出它的后序遍历。
输入输出格式
输入格式:
共2行。
第一行,1个整数n。(1<=n<=300000)
第二行,n个数,代表泡泡的大小。
输出格式:
共2行。
第一行,输出树的深度。
第二行,输出数的后序遍历。
详见样例输出。
输入输出样例
输入样例#1: 复制
8
1 4 3 9 10 35 2 7
输出样例#1: 复制
deep=5
2
3
7
35
10
9
4
1
说明
水题一道。
思路:模拟堆
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int n,cnt,deep,bns,root;
struct data{
int ls,rs,val;
}tr[];
int max(int a,int b){
if(a<b) return b;
else return a;
}
void insert(int& rt,int x){
++bns;
if(!rt){ rt=++cnt;tr[rt].val=x;deep=max(deep,bns);return; }
if(x>tr[rt].val) insert(tr[rt].rs,x);
else insert(tr[rt].ls,x);
return;
}
void dfs(int rt){
if(tr[rt].ls) dfs(tr[rt].ls);
if(tr[rt].rs) dfs(tr[rt].rs);
printf("%d\n",tr[rt].val);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
bns=;int x;
scanf("%d",&x);
insert(root,x);
}
printf("deep=%d\n",deep);
dfs(root);
}