当前位置：首页 > JavaScript

js实现树

2026-02-01 05:58:07JavaScript

实现树结构的基本方法

在JavaScript中实现树结构通常涉及创建节点（Node）和树（Tree）类，节点包含数据和子节点的引用，树类提供操作方法如插入、删除、遍历等。

定义节点类 每个节点包含数据（value）和子节点（children）：

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

定义树类 树类包含根节点和操作方法：

class Tree {
  constructor() {
    this.root = null;
  }

  // 插入节点（需指定父节点）
  insert(value, parentValue) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this._insertNode(this.root, newNode, parentValue);
  }

  _insertNode(currentNode, newNode, parentValue) {
    if (currentNode.value === parentValue) {
      currentNode.children.push(newNode);
      return;
    }
    for (const child of currentNode.children) {
      this._insertNode(child, newNode, parentValue);
    }
  }
}

树的遍历方法

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

class Tree {
  // ...其他代码
  traverseDFS(callback) {
    this._traverseDFSNode(this.root, callback);
  }

  _traverseDFSNode(node, callback) {
    callback(node.value);
    for (const child of node.children) {
      this._traverseDFSNode(child, callback);
    }
  }
}

广度优先遍历（BFS） 使用队列实现层级遍历：

class Tree {
  // ...其他代码
  traverseBFS(callback) {
    const queue = [this.root];
    while (queue.length > 0) {
      const currentNode = queue.shift();
      callback(currentNode.value);
      queue.push(...currentNode.children);
    }
  }
}

实际应用示例

创建树并操作

const tree = new Tree();
tree.insert(1);          // 根节点
tree.insert(2, 1);       // 子节点
tree.insert(3, 1);       // 子节点
tree.insert(4, 2);       // 孙子节点

// 遍历示例
tree.traverseDFS(console.log); // 输出: 1, 2, 4, 3
tree.traverseBFS(console.log); // 输出: 1, 2, 3, 4

特殊树结构的实现

二叉树实现 限制每个节点最多有两个子节点：

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

二叉搜索树（BST）插入

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new BinaryTreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
}