JavaScript 树节点深度计算教程-js教程-PHP中文网

JavaScript 树节点深度计算教程

碧海醫心

发布： 2025-09-12 13:01:02

原创

537人浏览过

JavaScript 树节点深度计算教程

本教程详细介绍了如何在JavaScript中计算非二叉树节点的深度（或称层级）。通过两种递归方法，分别演示了如何从根节点出发按名称查找并计算深度，以及如何从目标节点出发向上回溯计算深度。文章提供了清晰的Node类定义、完整的示例代码和关键注意事项，帮助开发者理解并实现树节点深度的计算逻辑。

理解树节点深度

在树形数据结构中，节点的深度（depth）或层级（level）是指从根节点到该节点所经过的边的数量。通常，根节点的深度定义为0。例如，在一个树中：

                           root (深度 0)
                         /      \
                        A (深度 1) B (深度 1)
                       / \      / \
                      C   D    E   F (深度 2)
                    / \ \
                   G  H  I (深度 3)

登录后复制

节点 C 的深度是2，节点 G 的深度是3。本教程将提供两种基于递归的JavaScript实现方法来计算任意给定节点的深度。

节点结构定义

为了实现树节点的深度计算，我们首先需要定义一个基本的 Node 类。每个节点至少需要包含一个标识符（如 name）和其直接子节点的数组（children）。

class Node {
    constructor(name, ...children) {
        this.name = name;
        this.children = children;
    }
    // 后续深度计算方法将添加到此类中
}

登录后复制

这个 Node 类允许我们构建任意分支的非二叉树。children 参数使用剩余参数语法，方便在构造时直接传入子节点。

方法一：从根节点开始按名称查找并计算深度

这种方法从树的根节点开始遍历，尝试找到目标节点。一旦找到，就返回其相对于当前节点的深度。如果目标节点是当前节点本身，则深度为0；否则，它将是某个子节点的深度加1。

立即学习“Java免费学习笔记（深入）”；

实现思路：

基本情况： 如果当前节点的名称与目标名称匹配，则说明找到了目标节点，其深度为0。
递归步骤： 遍历当前节点的所有子节点。对每个子节点递归调用深度计算方法。
结果处理： 如果子节点的递归调用返回的深度值大于等于0（表示在子树中找到了目标节点），则当前节点的深度就是子节点返回的深度加1。
未找到情况： 如果遍历完所有子节点都没有找到目标节点，则返回 -1。

示例代码：

class Node {
    constructor(name, ...children) {
        this.name = name;
        this.children = children;
    }

    /**
     * 从当前节点开始，查找指定名称的节点并计算其深度。
     * @param {string} targetName 目标节点的名称。
     * @returns {number} 目标节点的深度（相对于调用此方法的节点），如果未找到则返回 -1。
     */
    getDepth(targetName) {
        // 基本情况：如果当前节点就是目标节点，深度为0
        if (this.name === targetName) {
            return 0;
        }

        // 递归步骤：遍历子节点
        for (const child of this.children) {
            const depth = child.getDepth(targetName); // 在子节点中查找
            // 如果在子树中找到了目标节点
            if (depth >= 0) {
                return depth + 1; // 目标节点的深度是子节点深度加1
            }
        }

        // 未在当前节点及其子树中找到目标节点
        return -1;
    }
}

// 构建示例树
const root = new Node("root",
    new Node("A",
        new Node("C",
            new Node("G"),
            new Node("H"),
            new Node("I")
        ),
        new Node("D")
    ),
    new Node("B",
        new Node("E"),
        new Node("F")
    )
);

// 计算节点 "C" 的深度
const depthC = root.getDepth("C");
console.log(`节点 "C" 的深度: ${depthC}`); // 输出: 节点 "C" 的深度: 2

// 计算节点 "I" 的深度
const depthI = root.getDepth("I");
console.log(`节点 "I" 的深度: ${depthI}`); // 输出: 节点 "I" 的深度: 3

// 计算不存在的节点 "X" 的深度
const depthX = root.getDepth("X");
console.log(`节点 "X" 的深度: ${depthX}`); // 输出: 节点 "X" 的深度: -1

登录后复制

注意事项：

算家云

高效、便捷的人工智能算力服务平台

查看详情

此方法要求从树的根节点调用，并传入目标节点的名称。
如果树中存在同名节点，此方法将返回第一个匹配到的节点的深度（通常是先序遍历中遇到的第一个）。
返回 -1 作为未找到的标识符，这是一种常见的做法。

方法二：从目标节点开始向上回溯计算深度

这种方法与前一种思路相反，它在目标节点上调用方法，并传入整个树的根节点。它通过检查当前节点是否是传入根节点的子节点来“向上”回溯，直到找到根节点。

实现思路：

基本情况： 如果当前节点就是传入的根节点，则其深度为0。
递归步骤： 遍历传入根节点的所有子节点。对每个子节点，递归调用深度计算方法，将当前节点（this）作为目标节点，将子节点作为新的“根”进行检查。
结果处理： 如果子节点的递归调用返回的深度值大于等于0（表示目标节点在子树中），则目标节点的深度就是子节点返回的深度加1。
未找到情况： 如果遍历完所有子节点都没有找到目标节点，则返回 -1。

示例代码：

class Node {
    constructor(name, ...children) {
        this.name = name;
        this.children = children;
    }

    /**
     * 从当前节点开始，向上回溯到指定根节点，计算当前节点的深度。
     * @param {Node} root 树的根节点。
     * @returns {number} 当前节点相对于传入根节点的深度，如果当前节点不在该根节点下则返回 -1。
     */
    getDepthWithRespectTo(root) {
        // 基本情况：如果当前节点就是根节点，深度为0
        if (this === root) {
            return 0;
        }

        // 递归步骤：遍历根节点的子节点，检查当前节点是否在其中
        // 注意：这里的“向上回溯”是通过检查目标节点是否是根节点的子节点来实现的
        for (const child of root.children) {
            // 在子节点中查找目标节点 (this)
            const depth = this.getDepthWithRespectTo(child);
            // 如果在子树中找到了目标节点
            if (depth >= 0) {
                return depth + 1; // 目标节点的深度是子节点深度加1
            }
        }

        // 未在当前根节点及其子树中找到目标节点
        return -1;
    }
}

// 构建示例树，并保持对节点 "C" 的引用
let nodeC;
const root = new Node("root",
    new Node("A",
        nodeC = new Node("C", // 将节点 "C" 赋值给 nodeC
            new Node("G"),
            new Node("H"),
            new Node("I")
        ),
        new Node("D")
    ),
    new Node("B",
        new Node("E"),
        new Node("F")
    )
);

// 计算节点 "C" 的深度，从节点 "C" 调用方法并传入根节点
const depthC = nodeC.getDepthWithRespectTo(root);
console.log(`节点 "C" 的深度: ${depthC}`); // 输出: 节点 "C" 的深度: 2

// 假设我们有节点 G 的引用
const nodeG = nodeC.children[0];
const depthG = nodeG.getDepthWithRespectTo(root);
console.log(`节点 "G" 的深度: ${depthG}`); // 输出: 节点 "G" 的深度: 3

登录后复制

注意事项：