有基础班_day03课上题目

zxcvbnm

2025-07-03 16:42:38

发布于：上海

19阅读

0回复

0点赞

题目
结点的度
先序遍历
中序遍历
后序遍历
求先序遍历

结点的度

题目大意

给定一棵以 $1$ 为根的树，共 $n$ 个结点，树用 $n-1$ 条边表示父子关系。你需要处理 $q$ 个查询，每次询问一个结点的度数。

题意分析

树是有向关系：输入中给定的是 $fa$ 是 $son$ 的父亲；
但我们要输出的是度数，即该结点连接的边数（子结点数量）；
因为输入的是有向边（从父到子），所以只需统计每个点作为父节点出现的次数即可。

解题思路

一、数组记录度数

用数组 $deg[i]$ 表示第 $i$ 个结点的度；
每读入一对边 $(fa, son)$ ，令 $deg[fa]++$ ；
每个子节点 $son$ 不需要处理（因为题目不问入度）；
对每个查询 $x$ ，输出 $deg[x]$ 即可。

时间复杂度分析

建树处理 $n-1$ 条边，时间 $O(n)$ ；
查询 $q$ 次，每次 $O(1)$ ；
总体时间复杂度： $\boxed{O(n + q)}$ ；
空间复杂度： $O(n)$ 。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int deg[N]; // 存储每个结点的度

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int fa, son;
        cin >> fa >> son;
        deg[fa]++; // 父节点度数 +1
    }

    int q;
    cin >> q;

    while (q--) {
        int x;
        cin >> x;
        cout << deg[x] << '\n';
    }

    return 0;
}

先序遍历

题目大意

给定一个长度为 $n$ 的数组，将其构造成完全二叉树的结构（根结点编号为 $1$ ，左儿子为 $2x$ ，右儿子为 $2x+1$ ），然后输出整棵二叉树的先序遍历结果。

题意分析

我们可以把数组想象成完全二叉树的顺序存储结构：

树的根是数组下标 $1$ ；
每个结点编号 $x$ ：
- 左儿子编号为 $2x$ ；
- 右儿子编号为 $2x+1$ ；
当 $x > n$ 时视为越界（无该结点）；
遍历顺序为：

$\text{先序遍历} = \text{根} \rightarrow \text{左子树} \rightarrow \text{右子树}$

解题思路

用数组 $a[1\sim n]$ 储存树的顺序结构；
定义一个递归函数 dfs(x)：
- 若 $x > n$ ：越界，返回；
- 否则：
  - 输出当前结点 a[x]；
  - 递归访问左儿子 dfs(2x)；
  - 递归访问右儿子 dfs(2x + 1)；

时间复杂度分析

树中最多访问每个结点一次；
总时间复杂度为 $\boxed{O(n)}$ 。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

// 先序遍历函数
void dfs(int x) {
    if (x > n) return;
    cout << a[x] << " ";
    dfs(2 * x);     // 左子树
    dfs(2 * x + 1); // 右子树
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1); // 从根节点开始遍历
    return 0;
}

中序遍历

题目大意

给定一个长度为 $n$ 的数组，将其构造成完全二叉树的结构（根结点编号为 $1$ ，左儿子为 $2x$ ，右儿子为 $2x+1$ ），然后输出整棵二叉树的中序遍历结果。

题意分析

我们可以把数组想象成完全二叉树的顺序存储结构：

树的根是数组下标 $1$ ；
每个结点编号 $x$ ：
- 左儿子编号为 $2x$ ；
- 右儿子编号为 $2x+1$ ；
当 $x > n$ 时视为越界（无该结点）；
遍历顺序为：

$\text{先序遍历} = \text{左子树} \rightarrow \text{根} \rightarrow \text{右子树}$

解题思路

用数组 $a[1\sim n]$ 储存树的顺序结构；
定义一个递归函数 dfs(x)：
- 若 $x > n$ ：越界，返回；
- 否则：
  - 递归访问左儿子 dfs(2x)；
  - 输出当前结点 a[x]；
  - 递归访问右儿子 dfs(2x + 1)；

时间复杂度分析

每个结点被访问一次；
总时间复杂度为 $\boxed{O(n)}$ ；
空间复杂度为递归栈深度，最坏为 $O(n)$ 。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

// 先序遍历函数
void dfs(int x) {
    if (x > n) return;
    dfs(2 * x);     // 左子树
    cout << a[x] << " ";
    dfs(2 * x + 1); // 右子树
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1); // 从根节点开始遍历
    return 0;
}

后序遍历

题目大意

给定一个长度为 $n$ 的数组，将其构造成完全二叉树的结构（根结点编号为 $1$ ，左儿子为 $2x$ ，右儿子为 $2x+1$ ），然后输出整棵二叉树的后序遍历结果。

题意分析

我们可以把数组想象成完全二叉树的顺序存储结构：

树的根是数组下标 $1$ ；
每个结点编号 $x$ ：
- 左儿子编号为 $2x$ ；
- 右儿子编号为 $2x+1$ ；
当 $x > n$ 时视为越界（无该结点）；
遍历顺序为：

$\text{先序遍历} = \text{左子树} \rightarrow \text{右子树} \rightarrow \text{根}$

解题思路

用数组 $a[1\sim n]$ 储存树的顺序结构；
定义一个递归函数 dfs(x)：
- 若 $x > n$ ：越界，返回；
- 否则：
  - 递归访问左儿子 dfs(2x)；
  - 递归访问右儿子 dfs(2x + 1)；
  - 输出当前结点 a[x]；

时间复杂度分析

每个结点被访问一次；
总时间复杂度为 $\boxed{O(n)}$ ；
空间复杂度为递归栈深度，最坏为 $O(n)$ 。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

// 先序遍历函数
void dfs(int x) {
    if (x > n) return;
    dfs(2 * x);     // 左子树
    dfs(2 * x + 1); // 右子树
    cout << a[x] << " ";
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1); // 从根节点开始遍历
    return 0;
}

求先序遍历

题目大意

给定一棵二叉树的：

中序遍历字符串
后序遍历字符串

请根据这两种遍历结果，重建这棵二叉树的结构，并输出它的 先序遍历。

题意分析

我们利用中序和后序遍历的性质：

后序遍历： 最后一个节点是当前子树的 根节点
中序遍历： 根节点左边是 左子树，右边是 右子树

通过递归不断划分左子树和右子树，就可以重建整个先序遍历。

解题思路

函数定义

设函数 func(s, t)：

参数 $s$ 为当前子树的 中序遍历字符串
参数 $t$ 为当前子树的 后序遍历字符串
根节点是 $t$ 的最后一个字符

步骤如下：

找根节点： $root = t.back()$
在中序中定位根的位置：分出左子树、右子树
递归处理左子树：
- 中序： $s[0, id-1]$
- 后序： $t[0, id-1]$
递归处理右子树：
- 中序： $s[id+1, end]$
- 后序： $t[id, end-1]$
先输出根，再递归左右子树（先序遍历顺序：根-左-右）

时间复杂度分析

每个结点最多处理一次；
每次字符串分割代价为 $O(n)$ ，但总的深度不超过 $n$ 层；
总体时间复杂度 $\boxed{O(n^2)}$ ，对于 $n \leq 8$ 足够。

代码实现

#include <iostream>
using namespace std;

void func(string in, string post) {
    if (in.empty()) return;

    // 根节点：后序遍历的最后一个字符
    char root = post.back();
    cout << root;

    // 在中序中找根的位置
    int id = in.find(root);

    // 左子树：in[0...id-1] 对应 post[0...id-1]
    func(in.substr(0, id), post.substr(0, id));

    // 右子树：in[id+1...] 对应 post[id...len-2]
    func(in.substr(id + 1), post.substr(id, post.size() - id - 1));
}

int main() {
    string in, post;
    cin >> in >> post;
    func(in, post);
    return 0;
}