当前位置：首页 > ai >正文

信奥赛CSP-J复赛集训（图和树专题）（9）：P2171 Hz吐泡泡

ai 2025/8/26 11:06:23

信奥赛CSP-J复赛集训（图和树专题）（9）：P2171 Hz吐泡泡

在这里插入图片描述

题目背景

Hz大大是一种可爱的动物（神）。他很喜欢吐泡泡（更喜欢写作业）。

题目描述

这天，Hz大大心血来潮，吐了n个不同的泡泡玩（保证没有重复的泡泡）。因为他还要写作业，所以他请你帮他把这些泡泡排序成树（左子树<=根<右子树）。输出它的后序遍历。

输入格式

共2行。

第一行，1个整数n。(1<=n<=300000)

第二行，n个数，代表泡泡的大小。

输出格式

共2行。

第一行，输出树的深度。

第二行，输出数的后序遍历。

详见样例输出。

输入输出样例 #1

输入 #1

8
1 4 3 9 10 35 2 7

输出 #1

deep=5
2
3
7
35
10
9
4
1

AC代码：

#include<bits/stdc++.h>
using namespace std;const int N = 3e5 + 10; // 定义最大节点数
int n, x, cnt = 0, ans; // cnt记录节点数量，ans记录最大深度// 定义树节点结构体
struct node {int v, l, r; // v为节点值，l和r为左右子节点的下标
} a[N];// 创建新节点并初始化
int create(int x) {cnt++;a[cnt].v = x;a[cnt].l = a[cnt].r = 0; // 初始化左右子节点为0return cnt;
}// 插入节点到二叉搜索树中
void insert(int &p, int x) {if (p == 0) { // 当前位置无节点，创建新节点p = create(x);return;}// 根据二叉搜索树规则插入左右子树if (x < a[p].v) insert(a[p].l, x);else insert(a[p].r, x);
}// 计算树的深度
void dfs(int p, int deep) {if (p == 0) { // 空节点，更新最大深度ans = max(ans, deep);return;}// 递归处理左右子树，深度加1dfs(a[p].l, deep + 1);dfs(a[p].r, deep + 1);
}// 后序遍历并输出
void hx(int p) {if (a[p].l) hx(a[p].l); // 遍历左子树if (a[p].r) hx(a[p].r); // 遍历右子树cout << a[p].v << endl; // 输出当前节点值
}int main() {cin >> n;int root = 0; // 根节点初始化为0for (int i = 1; i <= n; i++) {cin >> x;if (i == 1) root = create(x); // 第一个元素创建为根节点else insert(root, x); // 后续元素插入树中}dfs(root, 0); // 计算深度，初始深度为0cout << "deep=" << ans << endl; // 输出深度hx(root); // 后序遍历输出return 0;
}