普通树的读入与构建

ID: 2212

Tried: 186

Accepted: 45

Difficulty: 5

题目描述：

给定一棵 n 个节点的树，节点编号为 $1-n$ ，树的根节点固定为 1。我们有两种方式表示树的结构：

方式一：通过 n-1 条边的形式，每条边 u v 表示节点 u 和节点 v 之间存在一条边。
方式二：通过一个 father 数组，father[i] 表示节点 i+1 的父节点。

请你编写程序，读入树的结构并使用深度优先搜索遍历打印这棵树的节点编号。

为了输出统一，从根节点开始遍历，优先访问序号小的子节点。

输入：

输入包含三部分：

第一行包含一个整数 n，表示树的节点个数。
第二行包含一个整数 type，表示树的表示方式：
- 如果 type = 1，表示通过边的形式输入。
- 如果 type = 2，表示通过 father 数组输入。
如果 type = 1，接下来会有 n-1 行，每行两个整数 u v，表示树中节点 u 和节点 v 之间存在一条边。
如果 type = 2，接下来一行有 n 个整数，father[i] 表示节点 i+1 的父节点，其中 father[0] = 0，表示 1 号节点为根节点,没有父节点。

输出：

打印遍历这棵树的节点编号。

输入样例 1：

输出样例 1：

1 2 4 5 3

样例1图例：

输入样例 2：

5
2
0 1 1 2 2

输出样例 2：

1 2 4 5 3

数据范围：

$1 \leq n \leq 10^5$

深度优先搜索(Depth First Search , DFS)是一种用于遍历或搜索图（图可以是树、无向图、有向图等）的算法。它按照深度优先的策略，优先访问当前节点的下一层邻接节点，直到无法继续为止，再回溯到上一层。

你可以先粗略的理解为：DFS就是在图上做特定的递归， $DFS \subset 递归$

前言:通过【图论的存储】图的存储，我们已经学会怎么把图存进邻接表且怎么遍历。由于树是有向无环图，所以树的存储和遍历和图基本是一致的。而本节课主要是让大家熟悉在笔试中1.树的两种读入方式以及2.树的先序遍历。

第一种读入形式:边形式

存储：这种读入形式将树看成一张图进行读入，本质就是我们上节课所学的读入形式，所以我们可以直接使用邻接表直接存储。

但特别要注意的是，虽然树在定义上是有向图，但是在笔试中，读入的数据可能会不符合其定义。例如，树中的一条有向边从节点 1 指向节点 2，但在输入时可能会以 2 1 的形式读入(为什么笔试的时候后台数据会存在这种不合理的地方，这就说来话长了...大家可以当作一个坑点)。所以为了能够正确进行遍历，我们需要使用无向图的存储方式(也就是对于读入进来的边，正反都存储一遍)。

遍历:由于存储结构被迫变成了无向图(虽然它本应该是有向图的结构)，那么在递归遍历的时候(或者说在深度优先搜索的过程中)，我们需要注意由于返祖边的存在导致的无限递归。

返祖边:假设树里存在一条从节点 1 指向节点 2的有向边1 2。那么1是2的父亲，也是2的祖先。但在实际的存储中又存在从2指向1的边2 1。那么2 1 就是一条返祖边。

为了解释无限递归确实存在，我们先看一段常规的DFS遍历树的代码：

def dfs(u):
    for v in adjList[u]:
    	dfs(v, u)  # 递归访问子节点
...
dfs(1) # 外部调用根节点进行搜索 , 大部分题目假设1是树的根，也就是提示你需要从1开始搜索。

对于每一个节点，我们递归地访问儿子节点，这就是所谓的深度优先搜索(depth first search , dfs)。下面是一颗根是1的树的一种可能的搜索顺序以及它的邻接表结构。

但是由于我们需要实际存储为无向边形式，那么下面这棵树就将无限的进行递归，永远无法结束。

解决方法:增加父亲参数father

在上述递归过程中，发生无限递归的关键因素是返祖边的存在，父子之间无限递归。那么如果对于所有节点，我们都禁止它访问父节点，问题不就解决了么~

def dfs(u , father):
    for v in adjList[u]:
        if v != father: # 禁止访问父亲节点
	    	dfs(v, u)  # 递归访问子节点
...
dfs(1 , -1) # 外部调用根节点进行搜索. 由于根节点没有父亲节点，需要设置为一个 不在<节点编号集合>里的数，通常设置为-1 / 0.

第二种读入形式：父亲数组

树中的每个节点都有唯一的父节点，这种唯一性使得我们可以通过数组来存储父节点信息。所以树可以用父亲数组（father[]）来表示树的结构。

示例 1：一棵简单的树

树的结构：

父亲数组表示：

father[1] = 0  （根节点无父节点，约定为 0）
father[2] = 1  （节点 2 的父亲是 1）
father[3] = 1  （节点 3 的父亲是 1）
father[4] = 3  （节点 4 的父亲是 3）
father[5] = 3  （节点 5 的父亲是 3）

父亲数组：father = [0, 1, 1, 3, 3]

由于我们访问的顺序是从父亲到儿子，而父亲数组存储的是每个儿子的父亲。所以我们无法直接利用父亲数组进行DFS。我们还是将父亲数组转化为邻接表进行存储

adjList[father[i]].append(i)

遍历:在这种读入形式下，不再存在第一种形式所提及的无限递归问题。可以直接进行遍历。

关键步骤

step1:排序

for i in range(1, n + 1):
    adjList[i].sort() # 针对int类型，sort默认为从小到大排序。

step2:遍历

def dfs(node, father):
    traversal_result.append(node)  # 先访问当前节点
    for child in adjList[node]:
        if child != father:  # 避免回到父节点
            dfs(child, node)  # 递归访问子节点

完整代码

def dfs(node, father):
    traversal_result.append(node)  # 先访问当前节点
    for child in adjList[node]:
        if child != father:  # 避免回到父节点
            dfs(child, node)  # 递归访问子节点


# 主程序
n = int(input())  # 读取节点数
tree_type = int(input())  # 读取表示方式

adjList = [[] for _ in range(n + 1)]  # 邻接表
traversal_result = []  # 存储遍历结果

if tree_type == 1:
    # 方式一：通过边的形式输入
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adjList[u].append(v)  # 添加子节点
        adjList[v].append(u)  # 添加父节点（无向树）
elif tree_type == 2:
    # 方式二：通过father数组输入
    father = list(map(int, input().split()))
    for i in range(1, n + 1):
        if father[i-1] != 0:
            adjList[father[i-1]].append(i)  # 添加子节点
            #adjList[i].append(father[i-1])  # 添加父节点

# 为了保证遍历顺序的一致性，先对每个节点的子节点进行排序
for i in range(1, n + 1):
    adjList[i].sort()

# 执行dfs，根节点为1，父节点为0（无）
dfs(1, 0)

# 输出遍历结果
print(" ".join(map(str, traversal_result)))

Java代码

import java.util.*;

public class Main {

    static List<List<Integer>> adjList;
    static List<Integer> traversalResult;

    public static void dfs(int node, int parent) {
        traversalResult.add(node); // 访问当前节点
        for (int child : adjList.get(node)) {
            if (child != parent) { // 避免回到父节点
                dfs(child, node); // 递归访问子节点
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取节点数
        int n = scanner.nextInt();
        // 读取表示方式
        int treeType = scanner.nextInt();

        adjList = new ArrayList<>();
        traversalResult = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        if (treeType == 1) {
            // 方式一：通过边的形式输入
            for (int i = 0; i < n - 1; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                adjList.get(u).add(v); // 添加子节点
                adjList.get(v).add(u); // 添加父节点（无向树）
            }
        } else if (treeType == 2) {
            // 方式二：通过father数组输入
            int[] father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = scanner.nextInt();
            }
            for (int i = 1; i <= n; i++) {
                if (father[i - 1] != 0) {
                    adjList.get(father[i - 1]).add(i); // 添加子节点
                    //adjList.get(i).add(father[i - 1]); // 添加父节点
                }
            }
        }

        // 为了保证遍历顺序的一致性，先对每个节点的子节点进行排序
        for (int i = 1; i <= n; i++) {
            Collections.sort(adjList.get(i));
        }

        // 执行dfs，根节点为1，父节点为0（无）
        dfs(1, 0);

        // 输出遍历结果
        for (int i = 0; i < traversalResult.size(); i++) {
            System.out.print(traversalResult.get(i));
            if (i < traversalResult.size() - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 100005 // 假设最大节点数为10^5

vector<int> adjList[MAX]; // 邻接表
vector<int> traversalResult; // 存储先序遍历结果

// DFS的递归实现
void DFS(int node, int parent) {
	traversalResult.push_back(node); // 访问当前节点
	for(auto &child : adjList[node]) {
		if(child != parent) { // 避免回到父节点
			DFS(child, node); // 递归访问子节点
		}
	}
}

int main(){
	
	int n, type;
	cin >> n >> type; // 读取节点数和表示方式
	
	if(type == 1){
		// 方式一：通过边的形式输入
		for(int i = 0; i < n-1; i++){
			int u, v;
			cin >> u >> v;
			adjList[u].push_back(v); // 添加子节点
			adjList[v].push_back(u); // 添加父节点（无向树）
		}
	}
	else if(type == 2){
		// 方式二：通过father数组输入
		// father[1] = 0，表示根节点
		vector<int> father(n+1);
		for(int i = 1; i <= n; i++){
			cin >> father[i];
			if(father[i] != 0){
				adjList[father[i]].push_back(i); // 添加子节点
				adjList[i].push_back(father[i]); // 添加父节点
			}
		}
	}
	
	// 为了保证遍历顺序的一致性，先对每个节点的子节点进行排序
	for(int i = 1; i <= n; i++){
		sort(adjList[i].begin(), adjList[i].end());
	}
	
	// 执行DFS，根节点为1，父节点为0（无）
	DFS(1, 0);
	
	// 输出遍历结果
	for(int i = 0; i < traversalResult.size(); i++){
		if(i > 0) cout << ' ';
		cout << traversalResult[i];
	}
	
	return 0;
}

#P3993. 普通树的读入与构建

题目描述：

输入：

输出：

输入样例 1：

输出样例 1：

样例1图例：

输入样例 2：

输出样例 2：

数据范围：

示例 1：一棵简单的树

关键步骤

完整代码

Java代码

C++ 代码

Status

Development

Support

#P3993. 普通树的读入与构建 ⬅ 上一题 ➡ 下一题

普通树的读入与构建

题目描述：

输入：

输出：

输入样例 1：

输出样例 1：

样例1图例：

输入样例 2：

输出样例 2：

数据范围：

示例 1：一棵简单的树

关键步骤

完整代码

Java代码

C++ 代码

Status

Development

Support

#P3993. 普通树的读入与构建