Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。

简介: 【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]

在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函数将从给定节点开始,按照宽度优先的顺序访问所有可达节点。

相关文章
|
3天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
17 2
|
12天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)回归模型(GradientBoostingRegressor算法)项目实战
Python实现GBDT(梯度提升树)回归模型(GradientBoostingRegressor算法)项目实战
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
13天前
|
缓存 算法 NoSQL
Java中的分布式缓存与一致性哈希算法
Java中的分布式缓存与一致性哈希算法
|
16天前
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
16 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
26天前
|
算法 Java
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
19 3
|
26天前
|
机器学习/深度学习 数据采集 存储
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全
**摘要:** 这篇文章介绍了决策树作为一种机器学习算法,用于分类和回归问题,通过一系列特征测试将复杂决策过程简化。文章详细阐述了决策树的定义、构建方法、剪枝优化技术,以及优缺点。接着,文章讨论了集成学习,包括Bagging、Boosting和随机森林等方法,解释了它们的工作原理、优缺点以及如何通过结合多个模型提高性能和泛化能力。文中特别提到了随机森林和GBDT(XGBoost)作为集成方法的实例,强调了它们在处理复杂数据和防止过拟合方面的优势。最后,文章提供了选择集成学习算法的指南,考虑了数据特性、模型性能、计算资源和过拟合风险等因素。
21 0
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全
|
10天前
|
存储 算法 Java
分布式自增ID算法---雪花算法(SnowFlake)Java实现
分布式自增ID算法---雪花算法(SnowFlake)Java实现
|
15天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
20天前
|
数据采集 搜索推荐 算法
使用Java编写高效的搜索引擎算法
使用Java编写高效的搜索引擎算法