树的广度优先遍历(BFS)

前言

树的广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树数据结构的算法。
在广度优先遍历中，从根节点开始，按层级顺序逐层访问节点，先访问当前层级的所有节点，然后再访问下一层级的节点。

js代码实现

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); // a b c d e f g

go代码实现

package main

import "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) // a b c d e f g
}