JavaScript实现二叉树与多叉树：概念、遍历算法与代码详解
本文详细解析JavaScript中二叉树与多叉树的数据结构实现。涵盖二叉树的先序、中序、后序遍历算法，以及多叉树的先根与层次遍历方法。通过链式存储结构构建节点，提供完整的JavaScript构造函数与遍历代码示例，帮助开发者深入理解前端虚拟DOM等场景下的树形数据处理。
JavaScript树结构概述
数据结构中的“树”结构广为人知，本文将回顾二叉树与普通树的核心概念，并使用JavaScript语言进行具体实现。
在前端开发中，树结构的应用十分广泛，例如Vue框架中的虚拟DOM机制以及事件冒泡机制等都体现了这一数据结构的特点。
二叉树的实现与遍历
二叉树
--概念--
二叉树是一种特殊的树形结构，其核心特征是每个节点最多只能拥有两棵子树，即不存在度大于2的节点。此外，二叉树的子树严格区分左右顺序，不可随意交换。
下文涉及的二叉树相关示例，均基于以下这棵二叉树展开：
遍历二叉树（traversing binary tree）主要有三种常用方式，具体如下：
1）、先序遍历二叉树（根左右）
若二叉树为空，则执行空操作；否则执行以下步骤：
--访问根结点；
--先序遍历左子树；
--先序遍历右子树。
以上述二叉树为例，先序遍历的结果如下：
2）、中序遍历二叉树（左根右）
若二叉树为空，则执行空操作；否则执行以下步骤：
--中序遍历左子树；
--访问根结点；
--中序遍历右子树。
以上述二叉树为例，中序遍历的结果如下：
3）、后序遍历二叉树（左右根）
若二叉树为空，则执行空操作；否则执行以下步骤：
--后序遍历左子树；
--后序遍历右子树；
--访问根结点。
以上述二叉树为例，后序遍历的结果如下：
了解二叉树及其遍历方式后，接下来我们将使用JavaScript，采用链式存储结构来实现二叉树。
二叉树节点定义
首先，利用JavaScript构造函数创建二叉树节点，定义如下：
function TreeNode(){
this.data = null;//该节点数据
this.lchild = null;//左子树
this.rchild = null;//右子树
};构建二叉树
随后，通过遍历二叉树的算法来构建一棵完整的二叉树。以下展示采用先序序列建立二叉树的方法：
/*
*method:采用先序序列建立二叉树
*@params: nodeList（Array） --树节点，以先序序列存入数组中，null代表空节点
*/
TreeNode.createBiTree = function(nodeList){
var i = 0;
return (function getNode(){
var node = null,
val = nodeList[i++];
if(!val){
node = null;
}else{
node = new TreeNode();
node.data = val;
node.lchild = getNode();
node.rchild = getNode();
}
return node;
})();
};二叉树遍历算法
最后，实现二叉树的遍历功能，包括先序遍历（PreOrderTraverse）、中序遍历（InOrderTraverse）以及后序遍历（PostOrderTraverse），具体代码如下：
TreeNode.prototype = {
constructor: TreeNode,
_PreOrderTraverse: function(node){
if(node){
console.log(node.data);
this._PreOrderTraverse(node.lchild);
this._PreOrderTraverse(node.rchild);
}
},
PreOrderTraverse: function(){
console.log('PreOrder:');
this._PreOrderTraverse(this);
},
_InOrderTraverse: function(node){
if(node){
this._InOrderTraverse(node.lchild);
console.log(node.data);
this._InOrderTraverse(node.rchild);
}
},
InOrderTraverse: function(){
console.log('InOrder:');
this._InOrderTraverse(this);
},
_PostOrderTraverse: function(node){
if(node){
this._PostOrderTraverse(node.lchild);
this._PostOrderTraverse(node.rchild);
console.log(node.data);
}
},
PostOrderTraverse: function(){
console.log('PostOrder:');
this._PostOrderTraverse(this);
}
};利用上述二叉树示例，读者可自行运行测试代码验证结果：
var treeNode = null,
nodeList = ['A', 'B', 'C', null, null, 'D', 'E', null, 'G', null, null, 'F', null, null, null];
//getting a binary tree from nodeList
treeNode = TreeNode.createBiTree(nodeList);
//traversing the tree of treeNode
treeNode.PreOrderTraverse();//ABCDEGF
treeNode.InOrderTraverse();//CBEGDFA
treeNode.PostOrderTraverse();//CGEFDBA多叉树的实现与遍历
树
--概念--
树是n（n>=0）个结点的有限集。在任意非空树中，存在且仅存在一个特定的根（root）结点；当n>1时，其余结点可划分为m（m>0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。显然，二叉树属于树的范畴。
下文涉及的多叉树相关示例，均基于以下这棵树展开：
遍历一棵多孩子树，主要有两种常用遍历方式，具体如下：
1) 、先根遍历，其逻辑与深度优先搜索（Depth_First Search）类似。两者均利用栈来遍历元素，具体过程如下：
2) 、按层次遍历，其逻辑与广度优先搜索（Breadth_First Search）类似。两者均利用队列来遍历元素，具体过程如下：
了解树结构及其遍历方式后，接下来我们将使用JavaScript，同样采用链式存储结构来实现多叉树。
多叉树节点定义
首先，利用JavaScript定义多叉树的节点构造函数，如下：
/*
*@Params: data --节点数据
children -- 所有孩子结点
*/
function TreeNode(data, children){
if(!(this instanceof TreeNode)){
return new TreeNode(data, children);
}
this.data = data || null;
this.children = children || [];
};构建多叉树
基于上述TreeNode构造函数，可以将示例中的树表示为以下结构：
var treeNode = TreeNode('A', [
TreeNode('B', [TreeNode('E')]),
TreeNode('C'),
TreeNode('D')
]);多叉树遍历算法
接着，编写树的遍历方法，包括先根遍历和按层次遍历，具体代码实现如下：
TreeNode.prototype = {
constructor: TreeNode,
_traverseAsDFS: function(node){//先根遍历
var self = this;
if(node){
console.log(node.data);
node.children.forEach(function(child){
if(child.children.length){
self._traverseAsDFS(child);
}else{
console.log(child.data);
}
});
}
},
traverseAsDFS: function(){
console.log('Depth_First Search');
this._traverseAsDFS(this);
},
traverseAsBFS: function(){//按层次遍历
var queue = [];
console.log('Breadth_First Search');
console.log(this.data);
if(this.children.length){
queue.push(this);
}
while(queue.length){
let tempNode = queue.shift();
tempNode.children.forEach(function(child){
console.log(child.data);
if(child.children.length){
queue.push(child);
}
});
}
}
};利用上述多叉树示例，读者可自行运行测试代码验证结果：
var treeNode = TreeNode('A', [
TreeNode('B', [TreeNode('E')]),
TreeNode('C'),
TreeNode('D')
]);
treeNode.traverseAsDFS();//ABECD
treeNode.traverseAsBFS();//ABCDE上述所有完整代码已托管至GitHub，可供参考。
本文内容旨在帮助读者理解或应用于实际工作，欢迎支持本站。
JavaScript怎么遍历对象的Symbol键和不可枚举属性
2026-11-05 13:13:39
封装一个健壮的JS字符串判空工具函数
2026-11-05 12:16:14
JavaScript合并数组的三种常用方法：concat、扩展运算符与push
2026-11-05 11:22:29
JavaScript立即执行函数(IIFE)是什么及基本语法
2026-11-05 10:51:19
JS对象数组转字符串为什么推荐用JSON.stringify()
2026-11-05 09:40:31