当前位置：首页 > 全部内容 > 正文

JavaScript 多叉树实现：创建、添加、遍历与移除详解

作者：青柠

时间：2026-10-22

浏览：431

本文详细介绍 JavaScript 中多叉树数据结构的经典实现，涵盖节点创建、树结构构建、节点添加与移除，以及深度优先和广度优先遍历算法。通过具体代码示例，解析如何在 JS 中高效管理层级数据，如 DOM 树或文件系统目录结构。

文章目录

多叉树概述与节点构建

本文通过具体实例，详细讲解 JavaScript 中多叉树这一数据结构的经典操作方法。内容旨在为读者提供清晰的参考与学习素材。

多叉树适用于存储复杂的数据结构，借助遍历方法能够高效地查找数据，从而提升检索效率，并便于对节点数据进行统一管理。值得注意的是，JavaScript 中的 DOM 结构本质上就是以多叉树的形式进行存储的。接下来，我们将使用 JavaScript 代码来实现多叉树的数据结构。

1、创建一个节点

数据在结构中是以节点的形式进行存储的，具体实现如下：


class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}

2、构建多叉树

树结构用于连接各个节点，类似于现实世界中树木的主干，从中延伸出众多分支。

多叉树类与节点添加实现


class MultiwayTree {
  constructor() {
    this._root = null;
  }
}

3、添加节点


function add(data, toData, traversal) {
  let node = new Node(data)
  // 第一次添加到根节点
  // 返回值为this，便于链式添加节点
  if (this._root === null) {
    this._root = node;
    return this;
  }
  let parent = null,
    callback = function(node) {
      if (node.data === toData) {
        parent = node;
        return true;
      }
    };
  // 根据遍历方法查找父节点（遍历方法后面会讲到），然后把节点添加到父节点
  // 的children数组里
  // 查找方法contains后面会讲到
  this.contains(callback, traversal);
  if (parent) {
    parent.children.push(node);
    node.parent = parent;
    return this;
  } else {
    throw new Error('Cannot add node to a non-existent parent.');
  }
}

4、深度优先遍历（DFS）

深度优先遍历策略倾向于先深入子节点进行搜索，待子节点全部查找完毕后，再转向兄弟节点。这种遍历方式特别适合数据层级较深的场景，例如文件目录结构。

深度优先与广度优先遍历算法


function traverseDF(callback) {
  let stack = [], found = false;
  stack.unshift(this._root);
  let currentNode = stack.shift();
  while(!found && currentNode) {
    // 根据回调函数返回值决定是否在找到第一个后继续查找
    found = callback(currentNode) === true ? true : false;
    if (!found) {
      // 每次把子节点置于堆栈最前头，下次查找就会先查找子节点
      stack.unshift(...currentNode.children);
      currentNode = stack.shift();
    }
  }
}

5、广度优先遍历（BFS）

广度优先遍历则优先查找同一层的兄弟节点，逐层向下扩展。这种方式适用于子节点数量较多的情况，例如公司内部的岗位层级结构。


function traverseBF(callback) {
  let queue = [], found = false;
  queue.push(this._root);
  let currentNode = queue.shift();
  while(!found && currentNode) {
    // 根据回调函数返回值决定是否在找到第一个后继续查找
    found = callback(currentNode) === true ? true : false;
    if (!found) {
      // 每次把子节点置于队列最后，下次查找就会先查找兄弟节点
      queue.push(...currentNode.children)
      currentNode = queue.shift();
    }
  }
}

6、判断节点是否存在（包含节点）

节点存在性判断与移除操作


function contains(callback, traversal) {
  traversal.call(this, callback);
}

回调函数的算法可根据实际需求自行实现，具有较高的灵活性。

7、移除节点


// 返回被移除的节点
function remove(data, fromData, traversal) {
  let parent = null,
    childToRemove = null,
    callback = function(node) {
      if (node.data === fromData) {
        parent = node;
        return true;
      }
    };
  this.contains(callback, traversal);
  if (parent) {
    let index = this._findIndex(parent.children, data);
    if (index < 0) {
      throw new Error('Node to remove does not exist.');
    } else {
      childToRemove = parent.children.splice(index, 1);
    }
  } else {
    throw new Error('Parent does not exist.');
  }
  return childToRemove;
}

_findIndex 方法的实现逻辑如下：


function _findIndex(arr, data) {
  let index = -1;
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i].data === data) {
      index = i;
      break;
    }
  }
  return index;
}

完整的算法代码如下：


class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}
class MultiwayTree {
  constructor() {
    this._root = null;
  }
  //深度优先遍历
  traverseDF(callback) {
    let stack = [], found = false;
    stack.unshift(this._root);
    let currentNode = stack.shift();
    while(!found && currentNode) {
      found = callback(currentNode) === true ? true : false;
      if (!found) {
        stack.unshift(...currentNode.children);
        currentNode = stack.shift();
      }
    }
  }
  //广度优先遍历
  traverseBF(callback) {
    let queue = [], found = false;
    queue.push(this._root);
    let currentNode = queue.shift();
    while(!found && currentNode) {
      found = callback(currentNode) === true ? true : false;
      if (!found) {
        queue.push(...currentNode.children)
        currentNode = queue.shift();
      }
    }
  }
  contains(callback, traversal) {
    traversal.call(this, callback);
  }
  add(data, toData, traversal) {
    let node = new Node(data)
    if (this._root === null) {
      this._root = node;
      return this;
    }
    let parent = null,
      callback = function(node) {
        if (node.data === toData) {
          parent = node;
          return true;
        }
      };
    this.contains(callback, traversal);
    if (parent) {
      parent.children.push(node);
      node.parent = parent;
      return this;
    } else {
      throw new Error('Cannot add node to a non-existent parent.');
    }
  }
  remove(data, fromData, traversal) {
    let parent = null,
      childToRemove = null,
      callback = function(node) {
        if (node.data === fromData) {
          parent = node;
          return true;
        }
      };
    this.contains(callback, traversal);
    if (parent) {
      let index = this._findIndex(parent.children, data);
      if (index < 0) {
        throw new Error('Node to remove does not exist.');
      } else {
        childToRemove = parent.children.splice(index, 1);
      }
    } else {
      throw new Error('Parent does not exist.');
    }
    return childToRemove;
  }
  _findIndex(arr, data) {
    let index = -1;
    for (let i = 0, len = arr.length; i < len; i++) {
      if (arr[i].data === data) {
        index = i;
        break;
      }
    }
    return index;
  }
}

控制台测试代码示例


var tree = new MultiwayTree();
tree.add('a')
  .add('b', 'a', tree.traverseBF)
  .add('c', 'a', tree.traverseBF)
  .add('d', 'a', tree.traverseBF)
  .add('e', 'b', tree.traverseBF)
  .add('f', 'b', tree.traverseBF)
  .add('g', 'c', tree.traverseBF)
  .add('h', 'c', tree.traverseBF)
  .add('i', 'd', tree.traverseBF);
console.group('traverseDF');
tree.traverseDF(function(node) {
  console.log(node.data);
});
console.groupEnd('traverseDF');
console.group('traverseBF');
tree.traverseBF(function(node) {
  console.log(node.data);
});
console.groupEnd('traverseBF');
// 深度优先查找
console.group('contains1');
tree.contains(function(node) {
  console.log(node.data);
  if (node.data === 'f') {
    return true;
  }
}, tree.traverseDF);
console.groupEnd('contains1')
// 广度优先查找
console.group('contains2');
tree.contains(function(node) {
  console.log(node.data);
  if (node.data === 'f') {
    return true;
  }
}, tree.traverseBF);
console.groupEnd('contains2');
tree.remove('g', 'c', tree.traverseBF);

此处使用在线 HTML/CSS/JavaScript 代码运行工具：http://tools.jb51.net/code/HtmlJsRun 进行测试，运行效果如下所示：

多叉树概述与节点构建

感兴趣的朋友可以自行测试，查看具体的运行效果。

更多关于 JavaScript 相关内容感兴趣的读者，可查看本站专题：《JavaScript 数据结构与算法技巧总结》、《JavaScript 数学运算用法总结》、《JavaScript 排序算法总结》、《JavaScript 遍历算法与技巧总结》、《JavaScript 查找算法技巧总结》及《JavaScript 错误与调试技巧总结》。

希望本文所述的实现方法对大家学习 JavaScript 程序设计有所帮助。

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印，自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式，预览压缩前后的大小。

使用 ›
作者最新文章

let、const与var的区别：JavaScript变量声明最佳实践

JS中直接定义静态二维数组的字面量写法

JS 怎么查找字符串中所有匹配项的位置

JavaScript新手常犯的编码错误与最佳实践指南

为什么箭头函数不能直接用作JS立即执行函数

相关文章
热门文章
更多
CSS text-transform与JS修改首字母大写的适用场景区别
JS中constructor属性判断数组存在哪些风险
JS正则替换中$1捕获组引用与字符串重组技巧
全栈开发中JavaScript与Java怎么协作？前后端技术栈配合解析
Node.js后端生成高强度随机字符串的方法
怎么在本地运行JavaScript脚本：Node.js下载安装与环境配置教程
JS正则表达式基础：字面量与RegExp构造函数的区别及常用元字符
JS 解压出现乱码或报错怎么解决？
JavaScript常见SyntaxError语法错误排查与修复方法
JavaScript实现按钮点击冷却时间的完整代码示例