前言 树的广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树数据结构的算法。 在广度优先遍历中,从根节点开始,按层级顺序逐层访问节点,先访问当前层级的所有节点,然后再访问下一层级的节点。
js代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 function bfs (root ) { let queue = [root]; while (queue.length ) { let node = queue.shift (); console .log (node.val ); if (node.children ) { node.children .forEach (child => { queue.push (child); }) } } } const tree = { val : 'a' , children : [ { val : 'b' , children : [ { val : 'd' }, { val : 'e' } ] }, { val : 'c' , children : [ { val : 'f' }, { val : 'g' } ] } ] } bfs (tree);
go代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 package mainimport "fmt" type Node struct { Val string Child []*Node } func newNode (val string ) *Node { return &Node{ Val: val, Child: make ([]*Node, 0 ), } } func (n *Node) AddChild(children ...*Node) { n.Child = append (n.Child, children...) } func Bfs (root *Node) { queue := make ([]*Node, 0 ) queue = append (queue, root) for len (queue) > 0 { node := queue[0 ] queue = queue[1 :] fmt.Println(node.Val) if len (node.Child) > 0 { for _, child := range node.Child { queue = append (queue, child) } } } } func main () { a := newNode("a" ) b := newNode("b" ) c := newNode("c" ) d := newNode("d" ) e := newNode("e" ) f := newNode("f" ) g := newNode("g" ) a.AddChild(b, c) b.AddChild(d, e) c.AddChild(f, g) Bfs(a) }