17370845950

链表和树是JavaScript中处理动态与层级数据的关键结构。链表通过节点链接实现高效插入删除，适用于频繁修改的场景；树形结构如二叉树则用于表示层次关系，支持前序、中序、后序和层序遍历，常用于DOM、文件系统等。两者结合递归与指针操作，为算法设计提供基础支撑。

链表和树形结构是JavaScript中常见的数据结构，尤其在处理复杂逻辑、层级关系或动态数据时非常有用。下面分别介绍它们的基本概念与算法实现方式。

链表的实现

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。相比数组，链表在插入和删除操作上更高效。

定义节点结构：

每个节点包含两个部分：存储的数据和指向下一个节点的引用。

```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);
    }
}

实际应用场景

链表适合频繁插入删除的场景，如浏览器历史记录管理；树形结构适用于组织层级数据，比如菜单导航、分类目录等。

• 链表可用于实现栈和队列
• 二叉搜索树可提升查找效率（左小右大）
• 递归是处理树结构的常用方法

基本上就这些。掌握链表和树的基础实现，能为解决更复杂的算法问题打下坚实基础。