当前位置：首页 > JavaScript

js实现树

2026-03-14 04:19:47JavaScript

树的实现方法

在JavaScript中，树可以通过对象或类来实现。以下是几种常见的实现方式。

使用对象字面量

最简单的树结构可以通过嵌套对象来表示。每个节点包含一个值和一个子节点数组。

const tree = {
  value: 'root',
  children: [
    {
      value: 'child1',
      children: []
    },
    {
      value: 'child2',
      children: [
        {
          value: 'grandchild1',
          children: []
        }
      ]
    }
  ]
};

使用类实现

更结构化的方式是通过类定义树节点，这样可以方便地添加方法和属性。

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

  addChild(childNode) {
    this.children.push(childNode);
  }
}

const root = new TreeNode('root');
const child1 = new TreeNode('child1');
const child2 = new TreeNode('child2');
const grandchild1 = new TreeNode('grandchild1');

root.addChild(child1);
root.addChild(child2);
child2.addChild(grandchild1);

树的遍历

树的遍历通常分为深度优先（DFS）和广度优先（BFS）两种方式。

深度优先遍历（递归实现）

function dfs(node) {
  console.log(node.value);
  node.children.forEach(child => dfs(child));
}

广度优先遍历（队列实现）

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));
  }
}

二叉树实现

对于二叉树，每个节点最多有两个子节点（左和右）。

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new BinaryTreeNode('root');
root.left = new BinaryTreeNode('left');
root.right = new BinaryTreeNode('right');

树的应用示例

查找树中是否存在某个值（深度优先搜索）：

function containsValue(node, target) {
  if (node.value === target) return true;
  for (const child of node.children) {
    if (containsValue(child, target)) return true;
  }
  return false;
}

计算树的深度：

js实现树

function getTreeDepth(node) {
  if (node.children.length === 0) return 1;
  const childDepths = node.children.map(child => getTreeDepth(child));
  return 1 + Math.max(...childDepths);
}

这些方法展示了JavaScript中树的基本实现和操作。根据具体需求，可以扩展这些基础实现来满足更复杂的功能。

标签: js