输入若干行,每行描述了一组双亲节点和孩子节点的关系序偶对,输出该树的先根遍历序列
时间: 2024-03-09 10:49:44 浏览: 23
假设输入的每行数据格式为:`parent child1 child2 ...`,其中 `parent` 表示双亲节点,`child1`、`child2` 等表示该节点的孩子节点。假设树的节点数据结构如下:
```java
class TreeNode {
int val;
List<TreeNode> children;
}
```
其中 `val` 表示节点的值,`children` 表示该节点的子节点列表。
根据输入数据,可以先构建出一棵树。然后对该树进行先根遍历。
以下是完整的示例代码:
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Map<Integer, TreeNode> map = new HashMap<>();
while (scanner.hasNext()) {
String line = scanner.nextLine();
String[] tokens = line.split(" ");
int parentVal = Integer.parseInt(tokens[0]);
TreeNode parent = map.computeIfAbsent(parentVal, k -> new TreeNode(parentVal));
for (int i = 1; i < tokens.length; i++) {
int childVal = Integer.parseInt(tokens[i]);
TreeNode child = map.computeIfAbsent(childVal, k -> new TreeNode(childVal));
parent.children.add(child);
}
}
scanner.close();
// 先根遍历
List<Integer> result = new ArrayList<>();
preorderTraversal(map.get(1), result);
for (int val : result) {
System.out.print(val + " ");
}
}
private static void preorderTraversal(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
for (TreeNode child : root.children) {
preorderTraversal(child, result);
}
}
}
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
```
输入数据示例:
```
1 2 3
2 4 5
3 6
5 7
```
输出结果为:`1 2 4 5 7 3 6`。