js实现树
JavaScript 实现树结构
树是一种非线性数据结构，由节点和边组成，每个节点可以有零个或多个子节点。以下是几种常见的树实现方法。
使用对象实现树
通过对象和数组可以简单表示树结构，每个节点包含值和子节点数组。
const tree = {
value: 'A',
children: [
{
value: 'B',
children: [
{ value: 'D', children: [] },
{ value: 'E', children: [] }
]
},
{
value: 'C',
children: [
{ value: 'F', children: [] }
]
}
]
};使用类实现树
通过类定义树节点，更具面向对象特性，便于扩展方法。
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(childNode) {
this.children.push(childNode);
}
}
const root = new TreeNode('A');
const nodeB = new TreeNode('B');
const nodeC = new TreeNode('C');
root.addChild(nodeB);
root.addChild(nodeC);树的遍历方法
树的遍历分为深度优先（DFS）和广度优先（BFS）。
深度优先遍历（递归）
function dfs(node) {
console.log(node.value);
node.children.forEach(child => dfs(child));
}
dfs(tree);广度优先遍历（队列）
function bfs(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.value);
node.children.forEach(child => queue.push(child));
}
}
bfs(tree);二叉树实现
二叉树是每个节点最多有两个子节点的树结构。
class BinaryTreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
const root = new BinaryTreeNode('A');
root.left = new BinaryTreeNode('B');
root.right = new BinaryTreeNode('C');二叉树遍历
前序遍历
function preOrder(node) {
if (!node) return;
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}中序遍历
function inOrder(node) {
if (!node) return;
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}后序遍历
function postOrder(node) {
if (!node) return;
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
}应用场景
树结构适用于需要层级关系的场景，如文件系统、DOM树、路由配置等。选择合适的实现方式和遍历方法可以提高代码效率和可维护性。
