JavaScript数据结构_链表与树形结构算法实现-js教程-PHP中文网

JavaScript数据结构_链表与树形结构算法实现

幻影之瞳

发布： 2025-11-18 21:33:06

原创

885人浏览过

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

javascript数据结构_链表与树形结构算法实现

链表和树形结构是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(' -> '));
}

登录后复制

}

<H3>树形结构的实现</H3>
<p>树是一种非线性数据结构，常用于表示具有层级关系的数据，比如DOM结构、文件系统等。二叉树是最常见的形式，每个节点最多有两个子节点。</p>

<font color="#000">定义树节点：</font>
```javascript
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

登录后复制

二叉树的遍历算法：

创客贴设计

创客贴设计，一款智能在线设计工具，设计不求人，AI助你零基础完成专业设计！

150

查看详情

常见的遍历方式有前序、中序、后序和层序（广度优先）。

前序遍历（根-左-右）：

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

登录后复制