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

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

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

链表：单向链表的实现

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

基础实现：

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]