Trees and graphs can be implemented in JavaScript through objects and references; 2. Tree structures such as TreeNode classes support addChild, removeChild and DFS traversals; 3. Binary search tree (BST) realizes efficient search, insertion and in-order traversals through small left and large left rules; 4. Graphs are represented by adjacency tables (Map Sets), supporting the addition of vertices and edges, BFS and DFS traversals; 5. Practical suggestions include using Set to avoid duplicate edges, iteratively avoid stack overflow, and selecting BFS or DFS according to the scene, which can ultimately be expanded to weighted graphs or algorithm applications.

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 weighed edges.

? Tips & Best Practices

• Use Sets for adjacency lists to avoid duplicate edges.
• For weighed 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.

The above is the detailed content of JavaScript Data Structures: Implementing Trees and Graphs. For more information, please follow other related articles on the PHP Chinese website!