当前位置：首页 > 文章列表 > 文章 > 前端 > JavaScript链表树图算法实现详解

JavaScript链表树图算法实现详解

2025-12-04 11:49:52 0浏览收藏

一分耕耘，一分收获！既然打开了这篇文章《JavaScript链表树图算法实现解析》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

链表、树、图是JavaScript中核心数据结构。链表通过节点连接实现动态存储，支持尾插、指定位置插入与删除；树以二叉搜索树为例，实现节点插入、中序遍历与查找；图采用邻接表表示，支持添加顶点与边，并实现深度优先（DFS）和广度优先（BFS）遍历。三者分别适用于线性、层级与网状关系的数据处理，是算法设计与开发中的基础工具。

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

链表、树、图是JavaScript中常见的数据结构，它们在算法实现和实际开发中应用广泛。下面分别介绍这三种数据结构的基本实现方式及常用操作。

链表（Linked List）

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

节点定义：

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

单向链表实现：

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
// 在尾部添加节点
append(val) {
    const node = new ListNode(val);
    if (!this.head) {
        this.head = node;
    } else {
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this.size++;
}

// 插入节点到指定位置
insertAt(index, val) {
    if (index < 0 || index > this.size) return false;
    const node = new ListNode(val);
    if (index === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
    }
    this.size++;
    return true;
}

// 删除指定值的节点
remove(val) {
    if (!this.head) return null;
    if (this.head.val === val) {
        this.head = this.head.next;
        this.size--;
        return val;
    }
    let current = this.head;
    while (current.next && current.next.val !== val) {
        current = current.next;
    }
    if (current.next) {
        current.next = current.next.next;
        this.size--;
        return val;
    }
    return null;
}
}

树（Tree）— 二叉树与二叉搜索树

树是非线性结构，常用于表示层级关系。二叉树每个节点最多有两个子节点。

二叉树节点定义：

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

二叉搜索树（BST）实现：

class BST {
    constructor() {
        this.root = null;
    }
// 插入节点
insert(val) {
    const node = new TreeNode(val);
    if (!this.root) {
        this.root = node;
    } else {
        this._insertNode(this.root, node);
    }
}

_insertNode(root, node) {
    if (node.val < root.val) {
        if (!root.left) {
            root.left = node;
        } else {
            this._insertNode(root.left, node);
        }
    } else {
        if (!root.right) {
            root.right = node;
        } else {
            this._insertNode(root.right, node);
        }
    }
}

// 中序遍历（升序输出）
inorder(node = this.root, result = []) {
    if (node) {
        this.inorder(node.left, result);
        result.push(node.val);
        this.inorder(node.right, result);
    }
    return result;
}

// 查找节点
search(val, node = this.root) {
    if (!node) return null;
    if (val === node.val) return node;
    if (val < node.val) {
        return this.search(val, node.left);
    } else {
        return this.search(val, node.right);
    }
}
}

图（Graph）

图由节点（顶点）和边组成，可用于表示复杂关系网络。

图的邻接表实现：

class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }
// 添加顶点
addVertex(v) {
    if (!this.adjacencyList.has(v)) {
        this.adjacencyList.set(v, []);
    }
}

// 添加边（无向图）
addEdge(v, w) {
    this.addVertex(v);
    this.addVertex(w);
    this.adjacencyList.get(v).push(w);
    this.adjacencyList.get(w).push(v);
}

// 深度优先遍历（DFS）
dfs(start) {
    const visited = new Set();
    const result = [];

    const traverse = (vertex) => {
        if (!vertex) return;
        result.push(vertex);
        visited.add(vertex);
        this.adjacencyList.get(vertex).forEach(neighbor => {
            if (!visited.has(neighbor)) {
                traverse(neighbor);
            }
        });
    };

    traverse(start);
    return result;
}

// 广度优先遍历（BFS）
bfs(start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length) {
        const vertex = queue.shift();
        result.push(vertex);
        this.adjacencyList.get(vertex).forEach(neighbor => {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        });
    }
    return result;
}
}

这些基础实现涵盖了链表、树、图的核心操作。理解其原理有助于解决如路径查找、排序、递归等常见算法问题。基本上就这些，不复杂但容易忽略细节。

以上就是《JavaScript链表树图算法实现详解》的详细内容，更多关于JavaScript,算法,链表,图,树的资料请关注golang学习网公众号！

JavaScript 算法链表图树