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

相关文章
|
14天前
|
存储 算法 安全
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
|
14天前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
57 32
|
5天前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
2天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
31 6
|
2天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
27 5
|
13天前
|
存储 监控 算法
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。
|
13天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
37 2
|
8月前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
184 0
|
存储 算法 Java
数据结构算法学习打卡week2 (Java)
数据结构算法学习打卡week2 (Java)
80 0
|
Rust 算法 安全
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)

热门文章

最新文章