题目描述

在这道题中，我们需要处理一棵树的节点关系，并根据输入的节点查询其所有下层节点（子节点）。输入包括节点及其父节点的关系，最后输入一个查询节点。我们需要输出该节点的所有下层节点，并按照字典序排序。

思路

1. 数据结构选择：我们可以使用一个字典（哈希表）来存储树的结构。字典的键是父节点，值是一个列表，包含所有该父节点的子节点。

2. 输入处理：首先读取输入的数据，构建树的字典结构。

3. 查询处理：对于输入的查询节点，检查字典中是否存在该节点，如果存在，则获取其子节点列表，并进行排序。

4. 输出结果：最后，按照字典序输出所有的下层节点。

代码分析

1. 库的使用：使用了 <iostream> 进行输入输出，<vector> 和 <map> 存储树的结构，<algorithm> 进行排序。

2. 数据结构：

   • map<string, vector<string>> tree：使用 map 存储父节点到子节点的映射关系，vector 用于存储一个父节点的所有子节点。

3. 读取输入：通过循环读取节点关系，并填充到 tree 中。

4. 查询节点：

   • 使用 tree.find(query) 检查查询节点是否存在。
   • 如果存在，则取出子节点并进行字典序排序。

5. 输出结果：按照要求逐行输出结果。

cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

// 深度优先搜索获取所有下层节点
void dfs(const string& node, const map<string, vector<string>>& tree, set<string>& result) {
    if (tree.find(node) != tree.end()) {
        for (const string& child : tree.at(node)) {
            result.insert(child); // 插入子节点到结果集中
            dfs(child, tree, result); // 递归访问子节点
        }
    }
}

int main() {
    int n; // 存储输入行数
    cin >> n;
    cin.ignore(); // 忽略换行符

    map<string, vector<string>> tree; // 存储树的结构

    // 读取节点与父节点的关系
    for (int i = 0; i < n; ++i) {
        string child, parent;
        cin >> child >> parent;
        tree[parent].push_back(child); // 将子节点加入父节点的列表中
    }

    string query; // 查询节点
    cin >> query;

    set<string> childrenSet; // 用于存储所有下层节点
    dfs(query, tree, childrenSet); // 执行深度优先搜索

    // 将结果转为向量并排序
    vector<string> children(childrenSet.begin(), childrenSet.end());
    sort(children.begin(), children.end());

    // 输出下层节点
    for (const string& child : children) {
        cout << child << endl; // 输出下层节点
    }

    return 0;
}

python

def dfs(node, tree, result):
    if node in tree:
        for child in tree[node]:
            result.add(child)  # 插入子节点到结果集中
            dfs(child, tree, result)  # 递归访问子节点

def main():
    n = int(input())  # 存储输入行数
    tree = {}  # 存储树的结构

    # 读取节点与父节点的关系
    for _ in range(n):
        child, parent = input().split()
        if parent not in tree:
            tree[parent] = []
        tree[parent].append(child)  # 将子节点加入父节点的列表中

    query = input()  # 查询节点

    children_set = set()  # 用于存储所有下层节点
    dfs(query, tree, children_set)  # 执行深度优先搜索

    # 将结果转为列表并排序
    children = sorted(children_set)

    # 输出下层节点
    for child in children:
        print(child)  # 输出下层节点

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    
    // 深度优先搜索获取所有下层节点
    public static void dfs(String node, Map<String, List<String>> tree, Set<String> result) {
        if (tree.containsKey(node)) {
            for (String child : tree.get(node)) {
                result.add(child); // 插入子节点到结果集中
                dfs(child, tree, result); // 递归访问子节点
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 存储输入行数
        scanner.nextLine(); // 忽略换行符

        Map<String, List<String>> tree = new HashMap<>(); // 存储树的结构

        // 读取节点与父节点的关系
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            String child = parts[0];
            String parent = parts[1];

            // 将子节点加入父节点的列表中
            tree.putIfAbsent(parent, new ArrayList<>());
            tree.get(parent).add(child);
        }

        String query = scanner.nextLine(); // 查询节点

        Set<String> childrenSet = new HashSet<>(); // 用于存储所有下层节点
        dfs(query, tree, childrenSet); // 执行深度优先搜索

        // 将结果转为列表并排序
        List<String> children = new ArrayList<>(childrenSet);
        Collections.sort(children);

        // 输出下层节点
        for (String child : children) {
            System.out.println(child); // 输出下层节点
        }

        scanner.close(); // 关闭扫描器
    }
}

题目内容

通常使用多行的节点、父节点表示一棵树，比如

西安 陕西

陕西 中国

江西 中国

中国 亚洲

泰国 亚洲

输入一个节点之后，请打印出来树中他的所有下层节点

输入描述

第一行输入行数，下面是多行数据，每行以空格区分节点和父节点

接着是查询节点

输出描述

输出查询节点的所有下层节点。以字典序排序

备注

树中的节点是唯一的，不会出现两个节点，是同一个名字

样例1

输入

5
b a
c a
d c
e c
f d
c

输出

d
e
f