在Java中，树和图相关的算法主要包括二叉树遍历、深度优先搜索（DFS）和广度优先搜索（BFS）。以下是这些算法的实现示例。
二叉树遍历
二叉树遍历有三种常见的方法：前序遍历（根节点 -> 左子树 -> 右子树）、中序遍历（左子树 -> 根节点 -> 右子树）和后序遍历（左子树 -> 右子树 -> 根节点）。
public class BinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static void preOrderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
}
public static void inOrderTraversal(TreeNode root) {
if (root != null) {
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
}
public static void postOrderTraversal(TreeNode root) {
if (root != null) {
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
}
}
深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图的算法。它通过递归地访问每个节点的所有后代来工作。
import java.util.*;
public class DFS {
static class Node {
int value;
List<Node> neighbors;
Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
}
public static void dfs(Node node, Set<Node> visited) {
if (node == null || visited.contains(node)) {
return;
}
visited.add(node);
System.out.println("Visiting: " + node.value);
for (Node neighbor : node.neighbors) {
dfs(neighbor, visited);
}
}
}
在这个例子中，我们使用了一个简单的邻接列表表示图中的节点及其连接。dfs函数会递归地访问所有未被访问过的邻居节点。
广度优先搜索（BFS）
广度优先搜索是一种从一个节点开始，沿着最短路径访问所有可达节点的算法。通常使用队列来存储待访问的节点。
import java.util.*;
public class BFS {
static class Node {
int value;
List<Node> neighbors;
Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
}
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.println("Visiting: " + current.value);
for (Node neighbor : current.neighbors) {
queue.offer(neighbor);
}
}
}
}
在这个例子中，我们同样使用了一个简单的邻接列表表示图中的节点及其连接。bfs函数将从给定节点开始，按照宽度优先的顺序访问所有可达节点。
