网站空间支付方式,o2o网站建设代理商,wordpress插件免费吗,网站不兼容360浏览器OD统一考试 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
通常使用多行的节点、父节点表示一棵树#xff0c;比如#xff1a; 西安 陕西 陕西 中国 江西 中国 中国 亚洲 泰国 亚洲 输入一个节点之后#xff0c;请打印出来树中他的所有下层节点。
… OD统一考试 分值 200分 题解 Java / Python / C 题目描述
通常使用多行的节点、父节点表示一棵树比如 西安 陕西 陕西 中国 江西 中国 中国 亚洲 泰国 亚洲 输入一个节点之后请打印出来树中他的所有下层节点。
输入描述
第一行输入行数下面是多行数据每行以空格区分节点和父节点
接着是查询节点
输出描述
输出查询节点的所有下层节点。以字典序排序。
备注 树中的节点是唯一的不会出现两个节点是同一个名字
示例1
输入
5
b a
c a
d c
e c
f d
c输出
d
e
f题解 这道题是一个树的遍历问题首先构建树的结构然后深度优先遍历 (DFS) 树的某一节点收集其所有下层节点并按字典序排序输出。 Java、Python、C 代码中都定义了一个 Node 类表示树的节点包含节点名称和子节点列表。然后通过输入的边信息构建了这个树的结构最后进行 DFS 遍历。 下面是一些关键点的总结 树的表示 使用 Node 类表示树的节点通过 addChild 方法构建父子关系通过 dfs 方法进行深度优先遍历。DFS 遍历 递归地遍历树的节点将每个子节点的名称收集起来最后按字典序排序。输入处理 使用 ScannerJava、input()Python、cinC等方式读取输入。数据结构选择 在 Java 和 Python 中使用了 ArrayList 和列表list作为存储子节点的数据结构在 C 中使用了 vector。节点查找 通过构建的树结构可以通过输入的关键节点找到相应的节点然后进行 DFS 遍历。 总体而言这个问题是一个典型的树的深度优先遍历问题通过递归的方式遍历树的节点按字典序排序输出结果。 Java
import java.util.*;
/*** author code5bug*/
class Node {String name;ListNode children;public Node(String name) {this.name name;this.children new ArrayList();}void addChild(Node child) {children.add(child);}
}public class Main {public static void dfs(Node node, ListString collect) {for (Node child : node.children) {collect.add(child.name);dfs(child, collect);}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);MapString, Node nodeMap new HashMap();// 构建父子关系int n Integer.parseInt(scanner.nextLine());for (int i 0; i n; i) {String[] input scanner.nextLine().split( );String child input[0];String parent input[1];nodeMap.computeIfAbsent(child, Node::new);nodeMap.computeIfAbsent(parent, Node::new);nodeMap.get(parent).addChild(nodeMap.get(child));}ListString result new ArrayList();String keyword scanner.nextLine();dfs(nodeMap.get(keyword), result);result.stream().sorted(Comparator.naturalOrder()).forEach(System.out::println);}
}
Python
class Node:def __init__(self, name):self.name nameself.children []def addChild(self, child):self.children.append(child)# 缓存所有的节点
node_map {}
# 构建父子关系
for _ in range(int(input())):child, parent input().split()node_map.setdefault(child, Node(child))node_map.setdefault(parent, Node(parent))node_map[parent].addChild(node_map[child])def dfs(node, collect):收集所有的子节点的名称到 collect 中for child in node.children:collect.append(child.name)dfs(child, collect)result []
dfs(node_map[input()], result)
result.sort()
print(*result, sep\n)
C
#include iostream
#include unordered_map
#include vector
#include algorithmusing namespace std;class Node {
public:string name;vectorNode children;Node(){}Node(string name) : name(name) {}void addChild(const Node child) {children.push_back(child);}
};void dfs(const Node node, vectorstring collect) {for (const Node child : node.children) {collect.push_back(child.name);dfs(child, collect);}
}int main() {unordered_mapstring, Node node_map;int n;cin n;// 构建父子关系for (int i 0; i n; i) {string child, parent;cin child parent;node_map.emplace(child, Node(child));node_map.emplace(parent, Node(parent));node_map[parent].addChild(node_map[child]);}string keyword;cin keyword;vectorstring result;dfs(node_map[keyword], result);sort(result.begin(), result.end());for (const string name : result) {cout name endl;}return 0;
}
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
