首页 > 其他分享 >树的广度优先遍历

树的广度优先遍历

时间:2023-06-05 16:38:25浏览次数:37  
标签:node BFS 优先 遍历 queue add 广度 节点


树的广度遍历

       广度优先遍历又称宽度优先遍历,缩写为BFS,和深度优先遍历DFS不同的是深度优先是指的同一个树先将某节点所有子节点遍历完后再遍历其兄弟节点。而BFS是先把同一层级的节点遍历完后再遍历下一级的子节点。

BFS

       即同一层级遍历完然后到下一层级。

树的广度优先遍历_bfs

DFS

       将一个节点全部遍历完,再遍历该节点的兄弟节点。

树的广度优先遍历_图解dfs和bfs_02

代码实现(Java)

public static void bfs(Queue<TreeNode> queue,List<Integer> result,TreeNode root){
    queue.add(root);
    if (queue.size()>0){
    	//queue用于缓存
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left!=null){
                queue.add(node.left);
            }

            if (node.right!=null){
                queue.add(node.right);
            }
        }
    }
}

       

  1. BFS的代码稍微难于DFS,需要用一个辅助队列来缓存同一层级的元素。
  2. DFS是递归实现,BFS一般不用递归。


标签:node,BFS,优先,遍历,queue,add,广度,节点
From: https://blog.51cto.com/u_16151322/6417535

相关文章

  • 树之深度优先遍历算法详解(DFS实现) LeetCode94
           本文以如下树结构为例深度优先(DeepFirstSearch)       树的孩子称作子树,对于一个树进行深度优先遍历,即将其某一子树下所有节点遍历完再去遍历其他子树。遍历的顺序以根为参照可分为先序遍历,中序遍历,后序遍历。遍历方式描述先序遍历根左右中序遍历左根右后......
  • RTOS 优先级倒置
    问题背景在多任务实时操作系统(RealTimeMultitaskOperatingSystem,简称multi-taskRTOS)中,为实现多线程同时运行,OS需要实现一种多个任务之间的切换,即任务调度算法(或策略)。RTOS中,常见调度算法是优先级调度:每个任务(线程)分配一个优先级,按任务紧急状况来划分,一般优先级数值越小,优先......
  • 根据层序遍历结果来构建完全二叉树
    做实习笔试时遇到的一个题里用到了根据层序遍历的结果来构建二叉树。全部代码如下importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throw......
  • 【python基础】复杂数据类型-列表类型(排序/长度/遍历)
    1.列表数据元素排序在创建的列表中,数据元素的排列顺序常常是无法预测的。这虽然在大多数情况下都是不可避免的,但经常需要以特定的顺序呈现信息。有时候希望保留列表数据元素最初的排列顺序,而有时候又需要调整排列顺序。python提供了很多列表数据元素排序的方式,可根据情况选用。1......
  • File类:遍历文件夹的方法
        ......
  • 图的遍历
    引入:图的遍历是指从图的某一顶点出发按某种方法访问图中所有顶点,并且每个顶点只访问一次树是一种特殊的图,所以树的遍历可以看作是图的遍历的特殊化,但图的遍历要更复杂主要有两种遍历算法,广度优先和深度优先1.广度优先搜索BFS基本思想:1随机选定一个起始点v2从v出发访问v的......
  • Map系列集合的遍历方式三:Lambda
          ......
  • Map系列集合的遍历方式二:键值对
        ......
  • Map系列集合的遍历方式一:键找值
        ......
  • shell遍历当前目录下的文件,用去掉文件后缀的字符串替换文件中的文本
    今天写了一个shell,遍历当前目录下的文件,用每个文件的文件名去掉后缀的字符串替换文件中的一段字符串。 脚本如下:#!/bin/bashfile=`ls*.html`;echo$fileforitemin$filedofilename=${item%.*}echo$filenamesed-i"s/search('channel')/search('${fi......