链表和树是JavaScript中处理动态与层级数据的关键结构。链表通过节点链接实现高效插入删除，适用于频繁修改的场景；树形结构如二叉树则用于表示层次关系，支持前序、中序、后序和层序遍历，常用于DOM、文件系统等。两者结合递归与指针操作，为算法设计提供基础支撑。
链表和树形结构是JavaScript中常见的数据结构，尤其在处理复杂逻辑、层级关系或动态数据时非常有用。下面分别介绍它们的基本概念与算法实现方式。
链表的实现
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。相比数组，链表在插入和删除操作上更高效。
定义节点结构：
每个节点包含两个部分：存储的数据和指向下一个节点的引用。
立即学习“Java免费学习笔记（深入）”；
```javascript class ListNode { constructor(val) { this.val = val; this.next = null; } } ```链表类的基本操作：
实现一个简单的单向链表，支持插入、删除和遍历。
```javascript class LinkedList { constructor() { this.head = null; }// 在链表末尾添加节点
append(val) {
const newNode = new ListNode(val);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
// 删除指定值的节点
remove(val) {
if (!this.head) return;
if (this.head.val === val) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
// 遍历并打印所有节点
print() {
const result = [];
let current = this.head;
while (current) {
result.push(current.val);
current = current.next;
}
console.log(result.join(' -> '));
}}
树形结构的实现
树是一种非线性数据结构，常用于表示具有层级关系的数据，比如DOM结构、文件系统等。二叉树是最常见的形式，每个节点最多有两个子节点。
定义树节点： ```javascript class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } }
二叉树的遍历算法：
常见的遍历方式有前序、中序、后序和层序（广度优先）。
前序遍历（根-左-右）：
function preorder(root) {
if (root) {
console.log(root.val);
preorder(root.left);
preorder(root.right);
}
}中序遍历（左-根-右）：
function inorder(root) {
if (root) {
inorder(root.left);
console.log(root.val);
inorder(root.right);
}
}后序遍历（左-右-根）：
function postorder(root) {
if (root) {
postorder(root.left);
postorder(root.right);
console.log(root.val);
}
}层序遍历（使用队列）：
function levelOrder(root) {
if (!root) return;
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}实际应用场景
链表适合频繁插入删除的场景，如浏览器历史记录管理；树形结构适用于组织层级数据，比如菜单导航、分类目录等。
- 链表可用于实现栈和队列
- 二叉搜索树可提升查找效率（左小右大）
- 递归是处理树结构的常用方法
基本上就这些。掌握链表和树的基础实现，能为解决更复杂的算法问题打下坚实基础。
