JsTreeArray.md

Дерево — это структура данных, состоящая из узлов, где каждый узел содержит данные и ссылки на дочерние узлы. Деревья часто используются для представления иерархических данных.

Ниже приведен пример реализации дерева на JavaScript. В этом примере мы создадим простое дерево, где каждый узел может иметь несколько дочерних узлов.

Узел (Node)

Каждый узел содержит данные и массив дочерних узлов:

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

  // Добавление дочернего узла
  addChild(child) {
    this.children.push(child);
  }

  // Удаление дочернего узла
  removeChild(child) {
    this.children = this.children.filter(c => c !== child);
  }
}

Дерево (Tree)

Класс дерева содержит корневой узел и методы для работы с деревом:

class Tree {
  constructor(rootData) {
    this.root = new TreeNode(rootData);
  }

  // Поиск узла по значению (обход в ширину)
  find(data) {
    const queue = [this.root];

    while (queue.length > 0) {
      const currentNode = queue.shift();

      if (currentNode.data === data) {
        return currentNode;
      }

      for (const child of currentNode.children) {
        queue.push(child);
      }
    }

    return null;
  }

  // Обход дерева в глубину (рекурсивный)
  traverseDFS(node = this.root, callback) {
    callback(node);
    for (const child of node.children) {
      this.traverseDFS(child, callback);
    }
  }

  // Обход дерева в ширину
  traverseBFS(callback) {
    const queue = [this.root];

    while (queue.length > 0) {
      const currentNode = queue.shift();
      callback(currentNode);

      for (const child of currentNode.children) {
        queue.push(child);
      }
    }
  }
}

Пример использования

const tree = new Tree('root');

// Добавление дочерних узлов к корневому узлу
const child1 = new TreeNode('child1');
const child2 = new TreeNode('child2');
tree.root.addChild(child1);
tree.root.addChild(child2);

// Добавление дочерних узлов к child1
const child1_1 = new TreeNode('child1_1');
child1.addChild(child1_1);

// Поиск узла
const node = tree.find('child1_1');
console.log(node ? node.data : 'Not found'); // child1_1

// Обход дерева в глубину
console.log('DFS Traversal:');
tree.traverseDFS(tree.root, node => console.log(node.data));

// Обход дерева в ширину
console.log('BFS Traversal:');
tree.traverseBFS(node => console.log(node.data));

Вывод

Этот код реализует простое дерево с методами для добавления и удаления дочерних узлов, поиска узлов, а также обхода дерева в глубину (DFS) и в ширину (BFS).

JsTreeLinkedList.md

Давайте реализуем дерево на основе связных списков, чтобы вставка и получение элементов были более эффективными.

Узел (TreeNode)

Каждый узел будет содержать данные, ссылку на первого дочернего узла и ссылку на следующего брата (узел на том же уровне).

class TreeNode {
  constructor(data) {
    this.data = data;
    this.firstChild = null;
    this.nextSibling = null;
  }

  // Добавление дочернего узла
  addChild(child) {
    if (this.firstChild === null) {
      this.firstChild = child;
    } else {
      let current = this.firstChild;
      while (current.nextSibling !== null) {
        current = current.nextSibling;
      }
      current.nextSibling = child;
    }
  }

  // Удаление дочернего узла
  removeChild(child) {
    if (this.firstChild === null) {
      return;
    }

    if (this.firstChild === child) {
      this.firstChild = this.firstChild.nextSibling;
      return;
    }

    let current = this.firstChild;
    while (current.nextSibling !== null && current.nextSibling !== child) {
      current = current.nextSibling;
    }

    if (current.nextSibling === child) {
      current.nextSibling = current.nextSibling.nextSibling;
    }
  }
}

Дерево (Tree)

Класс дерева будет содержать корневой узел и методы для работы с деревом:

class Tree {
  constructor(rootData) {
    this.root = new TreeNode(rootData);
  }

  // Поиск узла по значению (обход в ширину)
  find(data) {
    const queue = [this.root];

    while (queue.length > 0) {
      const currentNode = queue.shift();

      if (currentNode.data === data) {
        return currentNode;
      }

      let child = currentNode.firstChild;
      while (child !== null) {
        queue.push(child);
        child = child.nextSibling;
      }
    }

    return null;
  }

  // Обход дерева в глубину (рекурсивный)
  traverseDFS(node = this.root, callback) {
    callback(node);
    let child = node.firstChild;
    while (child !== null) {
      this.traverseDFS(child, callback);
      child = child.nextSibling;
    }
  }

  // Обход дерева в ширину
  traverseBFS(callback) {
    const queue = [this.root];

    while (queue.length > 0) {
      const currentNode = queue.shift();
      callback(currentNode);

      let child = currentNode.firstChild;
      while (child !== null) {
        queue.push(child);
        child = child.nextSibling;
      }
    }
  }
}

Пример использования

const tree = new Tree('root');

// Добавление дочерних узлов к корневому узлу
const child1 = new TreeNode('child1');
const child2 = new TreeNode('child2');
tree.root.addChild(child1);
tree.root.addChild(child2);

// Добавление дочерних узлов к child1
const child1_1 = new TreeNode('child1_1');
child1.addChild(child1_1);

// Поиск узла
const node = tree.find('child1_1');
console.log(node ? node.data : 'Not found'); // child1_1

// Обход дерева в глубину
console.log('DFS Traversal:');
tree.traverseDFS(tree.root, node => console.log(node.data));

// Обход дерева в ширину
console.log('BFS Traversal:');
tree.traverseBFS(node => console.log(node.data));

Вывод

Этот код реализует дерево на основе связных списков, где каждый узел содержит ссылки на первого дочернего узла и на следующего брата. Это позволяет эффективно добавлять и удалять узлы, а также обходить дерево в глубину (DFS) и в ширину (BFS).