javascript如何实现数据结构_链表和二叉树如何实现-js教程-PHP中文网

javascript如何实现数据结构_链表和二叉树如何实现

幻影之瞳

发布： 2025-12-16 17:24:07

原创

215人浏览过

JavaScript中链表和二叉树通过对象属性（如next、left、right）模拟指针实现，无需底层内存操作；链表以head为入口，BST按大小关系插入左右子节点，核心在于引用建模与递归/迭代逻辑。

javascript如何实现数据结构_链表和二叉树如何实现

JavaScript 中实现链表和二叉树，核心是用对象（或类）模拟节点结构，通过引用（指针）连接节点。不需要底层内存操作，靠 next、left、right 等属性维护逻辑关系。

链表：单向链表的实现

每个节点包含数据和指向下一个节点的引用。头节点（head）是入口，尾节点的 next 为 null。

基础实现：

PHP5 和 MySQL 圣经

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

485

查看详情

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

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

  // 头插法
  prepend(val) {
    this.head = new ListNode(val, this.head);
  }

  // 尾插法（需遍历到末尾）
  append(val) {
    const newNode = new ListNode(val);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = newNode;
  }

  // 遍历打印
  traverse() {
    const values = [];
    let curr = this.head;
    while (curr) {
      values.push(curr.val);
      curr = curr.next;
    }
    return values;
  }
}

// 使用示例
const list = new LinkedList();
list.append(1);
list.append(2);
list.prepend(0);
console.log(list.traverse()); // [0, 1, 2]

登录后复制

二叉树：二叉搜索树（BST）的实现

每个节点最多两个子节点：left（值更小）、right（值更大）。支持插入、查找、中序遍历等操作。

基础实现：

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

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

  insert(val) {
    const newNode = new TreeNode(val);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this._insertNode(this.root, newNode);
  }

  _insertNode(node, newNode) {
    if (newNode.val < node.val) {
      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);
      }
    }
  }

  // 中序遍历 → 得到升序数组
  inorder() {
    const result = [];
    const traverse = (node) => {
      if (!node) return;
      traverse(node.left);
      result.push(node.val);
      traverse(node.right);
    };
    traverse(this.root);
    return result;
  }
}

// 使用示例
const bst = new BinarySearchTree();
[5, 3, 7, 2, 4, 6, 8].forEach(x => bst.insert(x));
console.log(bst.inorder()); // [2, 3, 4, 5, 6, 7, 8]

登录后复制