JavaScript: Построение двоичного дерева

Обновлено: 14 сент., 13:16
626
Студентов
86%
Завершения

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

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

Двоичное дерево поиска

Node.js

Реализуйте и экспортируйте по умолчанию класс, который реализует представление узла.

Класс должен содержать:

  • Геттер getKey() — возвращает ключ.
  • Геттеры getLeft(), getRight() — возвращают соответственно левого и правого ребёнка. Если ребёнок в узле отсутствует, геттер возвращает null.
  • Метод insert(key) — выполняет добавление узла, формируя правильное двоичное дерево.

Примеры

const tree = new Node();
tree.insert(9);
tree.insert(17);
tree.insert(4);
tree.insert(3);
tree.insert(6);

tree.getKey(); // 9
tree.getLeft().getKey(); // 4
tree.getRight().getKey(); // 17
tree.getLeft().getLeft().getKey(); // 3
tree.getLeft().getRight().getKey(); // 6

Подсказки

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Отзывы

Аватар пользователя Askarov Alikhan
Askarov Alikhan 15 сентября 2020

крутая задачка, после предыдущей (поиск в двоичном дереве) и второго проекта, задачи такого типа (рекурсия) решаются в кайф. У кого проблема с рекурсией, настоятельная рекомендация пройти 2ой проект