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（值更大）。支持插入、查找、中序遍历等操作。
PHP5 和 MySQL 圣经
下载
本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。
立即学习“Java免费学习笔记（深入）”；
基础实现：
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]
实用建议与注意点
- 链表操作注意边界：空链表时
head === null，插入/删除前先判空 - BST 插入依赖比较逻辑，确保
val类型可比（如都是数字或都转字符串） - 递归实现简洁但要注意栈深度；高频操作可用迭代版本避免爆栈
- 调试时可加
toString()或printTree()方法可视化结构（比如缩进打印）
扩展方向
- 双向链表：节点加
prev属性，支持反向遍历 - 平衡二叉树（AVL / Red-Black）：需维护高度或颜色，自动旋转调整，复杂度高但保证 O(log n)
- 用 ES6 Map/Set 模拟简单邻接表链表（适合图算法），但非传统链表语义
