用java语言,写一个深度遍历代码
时间: 2023-03-12 20:51:44 浏览: 58
我可以为你提供一个使用 Java 语言编写的深度遍历代码的示例:
public class DeepTraversal {
public void traverse(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.getVal() + " ");
traverse(root.getLeft());
traverse(root.getRight());
}
}
相关问题
用java写一个深度优先遍历图算法
深度优先遍历(Depth-First Search, DFS)是一种常用的图遍历算法,下面是使用Java语言实现的伪代码:
```
public void dfs(int node, boolean[] visited, Map<Integer, List<Integer>> graph) {
// 标记当前节点已经被访问
visited[node] = true;
// 处理当前节点
System.out.print(node + " ");
// 遍历当前节点的所有邻居节点
for (int neighbor : graph.get(node)) {
// 如果邻居节点没有被访问过,则递归访问它
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
// 使用深度优先遍历遍历整张图
public void dfsTraversal(Map<Integer, List<Integer>> graph) {
boolean[] visited = new boolean[graph.size()];
// 从每个未被访问过的节点开始遍历
for (int node : graph.keySet()) {
if (!visited[node]) {
dfs(node, visited, graph);
}
}
}
```
其中,`dfs`方法是一个递归方法,用于从当前节点开始进行深度优先遍历。`visited`数组用于标记每个节点是否已经被访问过,`graph`参数是一个邻接表,表示整张图。`dfsTraversal`方法则是使用深度优先遍历遍历整张图,其中使用一个循环遍历每个未被访问过的节点,并调用`dfs`方法进行遍历。
用java语言实现图的深度优先遍历并进行测试
首先,我们需要定义一个图的类,包含顶点数目,每个点的邻接表以及一个表示是否被访问过的 boolean 数组:
```java
import java.util.LinkedList;
public class Graph {
private int V; // 顶点数目
private LinkedList<Integer> adj[]; // 邻接表
private boolean visited[]; // 用于标记是否被访问过
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
visited = new boolean[v];
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 深度优先遍历
void DFS(int v) {
visited[v] = true;
System.out.print(v + " ");
for (int i : adj[v]) {
if (!visited[i])
DFS(i);
}
}
}
```
接下来,我们可以编写一个测试类来创建一个图并进行深度优先遍历:
```java
public class Test {
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("深度优先遍历的结果为:");
g.DFS(2);
}
}
```
在上面的代码中,我们创建了一个具有 4 个顶点的图,并添加了 6 条边。然后我们对图进行深度优先遍历,从第二个顶点开始遍历。
输出结果为:
```
深度优先遍历的结果为:
2 0 1 3
```
这表明深度优先遍历从第二个顶点开始,依次访问了其他顶点。