JavaScript数据结构_链表与树形结构实现-js教程-PHP中文网

JavaScript数据结构_链表与树形结构实现

夜晨

发布： 2025-11-21 21:25:02

原创

868人浏览过

链表和树可通过对象与引用实现；链表用于高效插入删除，树适用于查找与层级结构，JavaScript中二者均需手动构建节点与操作方法。

javascript数据结构_链表与树形结构实现

链表和树是JavaScript中常见的数据结构，尤其在处理动态数据和层级关系时非常有用。虽然JavaScript没有内置的链表或树类型，但我们可以用对象和引用轻松实现它们。下面分别介绍链表和树形结构的基本实现方式。

链表的实现

链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。最常见的链表是单向链表。

定义节点：

每个节点是一个对象，包含两个属性：data（存储数据）和next（指向下一个节点）。

立即学习“Java免费学习笔记（深入）”；

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

登录后复制

链表类的基本操作：

实现一个链表类，支持插入、删除、查找等操作。

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 在链表末尾添加节点
  append(data) {
    const newNode = new ListNode(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 在指定位置插入节点
  insertAt(index, data) {
    if (index === 0) {
      const newNode = new ListNode(data);
      newNode.next = this.head;
      this.head = newNode;
      return;
    }
    let current = this.head;
    for (let i = 0; i < index - 1 && current; i++) {
      current = current.next;
    }
    if (!current) throw new Error('Index out of bounds');
    const newNode = new ListNode(data);
    newNode.next = current.next;
    current.next = newNode;
  }

  // 删除指定值的第一个节点
  remove(data) {
    if (!this.head) return;
    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next && current.next.data !== data) {
      current = current.next;
    }
    if (current.next) {
      current.next = current.next.next;
    }
  }

  // 查找是否包含某个值
  contains(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) return true;
      current = current.next;
    }
    return false;
  }

  // 转为数组便于查看
  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    return result;
  }
}

登录后复制

使用示例：

PHP5 和 MySQL 圣经

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。

466

查看详情

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
console.log(list.toArray()); // [1, 2, 3]
list.insertAt(1, 1.5);
console.log(list.toArray()); // [1, 1.5, 2, 3]
list.remove(1.5);
console.log(list.toArray()); // [1, 2, 3]

登录后复制

树形结构的实现

树是一种分层数据结构，最常见的是二叉树，每个节点最多有两个子节点：左子节点和右子节点。

定义树节点：

class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

登录后复制

二叉搜索树（BST）实现：

二叉搜索树满足：左子树所有节点值小于根节点，右子树所有节点值大于根节点。

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

  // 插入节点
  insert(data) {
    const newNode = new TreeNode(data);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this._insertNode(this.root, newNode);
  }

  _insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (!node.left) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (!node.right) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }

  // 查找节点
  search(data) {
    return this._searchNode(this.root, data);
  }

  _searchNode(node, data) {
    if (!node) return null;
    if (data === node.data) return node;
    return data < node.data 
      ? this._searchNode(node.left, data) 
      : this._searchNode(node.right, data);
  }

  // 中序遍历（左-根-右），输出有序序列
  inorderTraversal(node = this.root, result = []) {
    if (node) {
      this.inorderTraversal(node.left, result);
      result.push(node.data);
      this.inorderTraversal(node.right, result);
    }
    return result;
  }

  // 先序遍历（根-左-右）
  preorderTraversal(node = this.root, result = []) {
    if (node) {
      result.push(node.data);
      this.preorderTraversal(node.left, result);
      this.preorderTraversal(node.right, result);
    }
    return result;
  }

  // 后序遍历（左-右-根）
  postorderTraversal(node = this.root, result = []) {
    if (node) {
      this.postorderTraversal(node.left, result);
      this.postorderTraversal(node.right, result);
      result.push(node.data);
    }
    return result;
  }
}

登录后复制

使用示例：

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

console.log(bst.inorderTraversal());   // [3, 5, 7, 10, 15]
console.log(bst.preorderTraversal());  // [10, 5, 3, 7, 15]
console.log(bst.postorderTraversal()); // [3, 7, 5, 15, 10]

console.log(bst.search(7) !== null);   // true
console.log(bst.search(9) !== null);   // false

登录后复制

链表适合频繁插入删除的场景，而树适合快速查找、排序和层级表达。JavaScript通过对象引用来构建这些结构非常自然。理解它们的原理有助于写出更高效的代码。

基本上就这些。掌握基本实现后，可以进一步扩展功能，比如双向链表、平衡树、删除节点等复杂操作。

以上就是JavaScript数据结构_链表与树形结构实现的详细内容，更多请关注php中文网其它相关文章！