如何高效遍历JavaScript中的树形结构？

遍历树形结构

在JavaScript中，遍历树形结构是一种常见的操作，树形结构通常由节点组成，每个节点可以有零个或多个子节点，以下是一个简单的树形结构遍历的示例：

定义树形结构

我们定义一个树形结构的节点类：

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    addChild(child) {
        this.children.push(child);
    }
}

深度优先遍历（DFS）

深度优先遍历是一种递归遍历树的方法，它首先访问根节点，然后递归地访问子节点，以下是深度优先遍历的实现：

function depthFirstTraversal(node, callback) {
    if (node === null) return;
    callback(node.value); // 访问当前节点
    for (let child of node.children) {
        depthFirstTraversal(child, callback); // 递归访问子节点
    }
}

广度优先遍历（BFS）

广度优先遍历是一种非递归遍历树的方法，它使用队列来按层次顺序访问节点，以下是广度优先遍历的实现：

function breadthFirstTraversal(root, callback) {
    if (root === null) return;
    const queue = [root];
    while (queue.length > 0) {
        const currentNode = queue.shift(); // 取出队列的第一个元素
        callback(currentNode.value); // 访问当前节点
        for (let child of currentNode.children) {
            queue.push(child); // 将子节点加入队列
        }
    }
}

示例代码

// 创建树形结构
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const child3 = new TreeNode(4);
const child4 = new TreeNode(5);
root.addChild(child1);
root.addChild(child2);
child1.addChild(child3);
child1.addChild(child4);
// 深度优先遍历
console.log("Depthfirst traversal:");
depthFirstTraversal(root, value => console.log(value));
// 广度优先遍历
console.log("Breadthfirst traversal:");
breadthFirstTraversal(root, value => console.log(value));

相关问题与解答

问题1：如何修改深度优先遍历和广度优先遍历的代码，以便它们能够处理具有环的树形结构？

答案1： 为了处理具有环的树形结构，我们需要跟踪已经访问过的节点，以避免无限循环，我们可以使用一个集合来存储已访问过的节点，以下是修改后的深度优先遍历和广度优先遍历的代码：

function depthFirstTraversalWithCycleDetection(node, callback, visited = new Set()) {
    if (node === null || visited.has(node)) return;
    visited.add(node); // 标记节点为已访问
    callback(node.value); // 访问当前节点
    for (let child of node.children) {
        depthFirstTraversalWithCycleDetection(child, callback, visited); // 递归访问子节点
    }
}
function breadthFirstTraversalWithCycleDetection(root, callback) {
    if (root === null) return;
    const queue = [root];
    const visited = new Set(); // 用于检测环的集合
    while (queue.length > 0) {
        const currentNode = queue.shift(); // 取出队列的第一个元素
        if (visited.has(currentNode)) continue; // 如果节点已被访问，跳过
        visited.add(currentNode); // 标记节点为已访问
        callback(currentNode.value); // 访问当前节点
        for (let child of currentNode.children) {
            queue.push(child); // 将子节点加入队列
        }
    }
}

问题2：如何在遍历过程中收集节点的值？

答案2： 可以在回调函数中添加逻辑来收集节点的值，对于深度优先遍历，可以使用一个数组来收集值：

function collectValuesDFS(node, callback, values = []) {
    if (node === null) return;
    callback(node.value, values); // 访问当前节点并收集值
    for (let child of node.children) {
        collectValuesDFS(child, callback, values); // 递归访问子节点并收集值
    }
}

调用时，可以传递一个回调函数来收集值：

collectValuesDFS(root, (value, values) => values.push(value));
console.log(values); // 输出收集到的值的数组