樹和圖可通過對象和引用在JavaScript中實(shí)現(xiàn)；2. 樹結(jié)構(gòu)如TreeNode類支持 addChild、removeChild 和 DFS 遍歷；3. 二叉搜索樹（BST）通過左小右大規(guī)則實(shí)現(xiàn)高效查找、插入和中序遍歷；4. 圖使用鄰接表（Map Set）表示，支持添加頂點(diǎn)和邊、BFS和DFS遍歷；5. 實(shí)踐建議包括用Set避免重復(fù)邊、迭代避免棧溢出、根據(jù)場景選擇BFS或DFS，最終可擴(kuò)展至加權(quán)圖或算法應(yīng)用。

Trees and graphs are fundamental data structures in computer science, and while JavaScript doesn’t provide built-in classes for them, implementing them is straightforward and highly practical for solving real-world problems like file system navigation, organizational hierarchies, social networks, or routing algorithms.

Let’s walk through how to implement trees and graphs in JavaScript, focusing on clarity, usability, and common patterns.

? Implementing a Basic Tree

A tree is a hierarchical structure where each node has a value and zero or more children. A common type is the n-ary tree, where each node can have multiple children.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(value) {
    const childNode = new TreeNode(value);
    this.children.push(childNode);
    return childNode;
  }

  removeChild(value) {
    this.children = this.children.filter(child => child.value !== value);
  }

  // Traverse and print values (DFS)
  print(level = 0) {
    console.log("  ".repeat(level)   this.value);
    this.children.forEach(child => child.print(level   1));
  }
}

Usage Example:

const root = new TreeNode("A");
const b = root.addChild("B");
const c = root.addChild("C");
b.addChild("D");
b.addChild("E");
c.addChild("F");

root.print();
// Output:
// A
//   B
//     D
//     E
//   C
//     F

This structure is great for representing nested data like folders, comments in a thread, or DOM elements.

? Binary Tree & Binary Search Tree (BST)

A binary tree restricts nodes to at most two children: left and right. A Binary Search Tree (BST) adds ordering: left < parent < right.

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insert(value) {
    if (value < this.value) {
      if (this.left === null) {
        this.left = new BSTNode(value);
      } else {
        this.left.insert(value);
      }
    } else {
      if (this.right === null) {
        this.right = new BSTNode(value);
      } else {
        this.right.insert(value);
      }
    }
  }

  search(value) {
    if (value === this.value) return true;
    if (value < this.value && this.left) return this.left.search(value);
    if (value > this.value && this.right) return this.right.search(value);
    return false;
  }

  // In-order traversal (left → root → right)
  inOrder(values = []) {
    if (this.left) this.left.inOrder(values);
    values.push(this.value);
    if (this.right) this.right.inOrder(values);
    return values;
  }
}

Usage Example:

const bst = new BSTNode(10);
[5, 15, 3, 7, 12, 18].forEach(val => bst.insert(val));

console.log(bst.search(7));     // true
console.log(bst.search(9));     // false
console.log(bst.inOrder());     // [3, 5, 7, 10, 12, 15, 18]

BSTs are efficient for searching, insertion, and deletion (average O(log n)) when balanced.

? Implementing Graphs

A graph consists of nodes (vertices) connected by edges. Graphs can be:

• Directed or undirected
• Weighted or unweighted

We’ll use an adjacency list representation — a map where each key is a node, and its value is an array (or set) of connected nodes.

Undirected, Unweighted Graph

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, new Set());
    }
  }

  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).add(v2);
    this.adjacencyList.get(v2).add(v1); // Remove this line for directed graph
  }

  removeEdge(v1, v2) {
    this.adjacencyList.get(v1)?.delete(v2);
    this.adjacencyList.get(v2)?.delete(v1);
  }

  removeVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) return;

    for (const adjacent of this.adjacencyList.get(vertex)) {
      this.removeEdge(vertex, adjacent);
    }
    this.adjacencyList.delete(vertex);
  }

  // BFS traversal
  breadthFirst(start) {
    const queue = [start];
    const visited = new Set();
    const result = [];

    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return result;
  }

  // DFS traversal (iterative)
  depthFirst(start) {
    const stack = [start];
    const visited = new Set();
    const result = [];

    visited.add(start);

    while (stack.length > 0) {
      const vertex = stack.pop();
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          stack.push(neighbor);
        }
      }
    }

    return result;
  }
}

Usage Example:

const graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
graph.addEdge("D", "E");

console.log(graph.breadthFirst("A")); // ['A', 'B', 'C', 'D', 'E']
console.log(graph.depthFirst("A"));  // ['A', 'C', 'D', 'E', 'B'] (order may vary)

This implementation is flexible — you can easily extend it to support directed or weighted edges.

? Tips & Best Practices

• Use Sets for adjacency lists to avoid duplicate edges.
• For weighted graphs, store edges as objects: { node: 'B', weight: 5 }
• Always handle edge cases like missing nodes or disconnected graphs.
• Choose BFS for shortest path in unweighted graphs; DFS for deep exploration.
• Consider recursion for tree traversals, but use iteration for large graphs to avoid stack overflow.

Basically, trees and graphs in JavaScript come down to linking objects (nodes) and managing connections. Once you understand the patterns, you can adapt them to everything from autocomplete (tries) to network routing (Dijkstra’s algorithm). Not hard to start with — just build node by node.

以上是JavaScript數(shù)據(jù)結(jié)構(gòu)：實(shí)現(xiàn)樹和圖形的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！