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树、路由配置等。选择合适的实现方式和遍历方法可以提高代码效率和可维护性。