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

Обновлено: 14 сент., 15:06
147
Студентов
88%
Завершения

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

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

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

src/Node.php

Реализуйте метод insert($key), который выполняет добавление узла, формируя правильное двоичное дерево.

Примеры

<?php

use App\Node;

$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
тестов