树的遍历

// 定义一棵树
const tree = {
    value: 'A',
    children: [
        {
            value: 'B1',
            children: [
                {
                    value: 'C1',
                    children: null
                },
                {
                    value: 'C2',
                    children: null
                }
            ]
        },
        {
            value: 'B2',
            children: null
        },
        {
            value: 'B3',
            children: [
                {
                    value: 'C3',
                    children: null
                },
                {
                    value: 'C4',
                    children: null
                }
            ]
        },
    ]
}

深度优先遍历

按深度优先原则遍历树

遍历规则

• 访问根节点
• 对根节点的 children 依次进行深度优先遍历

// 深度优先遍历
// A B1 C1 C2 B2 B3 C3 C4
const dfs = (root) => {
    // 优先访问根节点
    console.log(root.value)
    // 遍历子节点
    root.children && root.children.forEach(item => {
        // 子节点继续按深度优先遍历
        dfs(item)
    });
}
dfs(tree)

广度优先遍历

优先访问离根节点最近的节点

遍历规则

• 新建一个队列，将根节点入队
• 将队头出队，访问队头
• 将子节点加入到队列
• 重复2、3步骤，直到整个队列为空

递归版
// 广度优先遍历
// A B1 B2 C1 C2 C3 C4
// 根节点入队
const queue = [tree]
const bfs = () => {
    // 队头出队
    const root = queue.shift()
    // 访问队头
    console.log(root.value)
    // 遍历子节点入队
    root.children && root.children.forEach(item => {
        queue.push(item)
    });
    // 重复上述步骤
    root.children && root.children.forEach(item => {
        bfs()
    });
}
bfs()
非递归版
const bfs = () => {
    const queue = []
    queue.push(tree)
    while(queue.length) {
        const root = queue.shift()
        console.log(root.value)
        root.children && root.children.forEach(item => {
            queue.push(item)
        })
    }
}