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（值更大）。支持插入、查找、中序遍历等操作。
立即学习“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 模拟简单邻接表链表（适合图算法），但非传统链表语义
