已知一棵树的节点间关系,请编程实现该树的先根遍历
时间: 2024-03-09 18:49:37 浏览: 64
树(孩子—兄弟链表表示)
5星 · 资源好评率100%
假设树的节点数据结构如下:
```java
class TreeNode {
int val;
List<TreeNode> children;
}
```
其中 `val` 表示节点的值,`children` 表示该节点的子节点列表。
可以使用递归实现先根遍历,具体实现如下:
```java
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
visit(root);
for (TreeNode child : root.children) {
preorderTraversal(child);
}
}
private void visit(TreeNode node) {
System.out.print(node.val + " ");
}
```
在 `preorderTraversal` 方法中,先访问根节点,然后遍历该节点的每个子节点,并分别对每个子节点进行递归遍历。在 `visit` 方法中,对节点进行操作,这里只是简单地输出节点的值。
使用示例:
```java
// 构造一棵树
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
root.children = Arrays.asList(node2, node3, node4);
node2.children = Arrays.asList(node5, node6);
// 先根遍历
preorderTraversal(root); // 输出:1 2 5 6 3 4
```
在该示例中,树的结构如下:
```
1
/ | \
2 3 4
/ \
5 6
```
先根遍历的结果为:1 2 5 6 3 4。
阅读全文