src/Node.php
Двоичное дерево поиска состоит из узлов, каждый из которых содержит значение ключа и два поддерева (левое и правое), которые в свою очередь также являются двоичными деревьями. Правильное дерево не содержит повторяющихся ключей, и для каждого узла гарантируется, что в левом поддереве все значения меньше текущего, а в правом — больше.
Реализуйте класс Node
, который реализует представление узла. Конструктор класса принимает на вход значение ключа (число), и двух детей, которые в свою очередь также являются узлами. Дерево может быть создано пустым.
Класс должен содержать методы:
- Геттер
getKey()
— возвращает ключ. Если дерево пустое, возвращаетnull
. - Геттеры
getLeft()
,getRight()
— возвращают соответственно левого и правого ребёнка. Если ребёнок в узле отсутствует, геттер возвращаетnull
. search(key)
— выполняет поиск узла в правильном двоичном дереве по ключу и возвращает узел. Если узел не найден, возвращаетсяnull
.
Примеры
<?php
use App\Node;
$tree = new Node(
9,
new Node(
4,
new Node(3),
new Node(
6,
new Node(5),
new Node(7)
)
),
new Node(
17,
null,
new Node(
22,
new Node(20),
null
)
)
);
$node = $tree->search(6);
$node->getKey(); // 6
$node->getLeft()->getKey(); // 5
$node->getRight()->getKey(); // 7
$tree->search(35); // null
$tree->search(3)->getLeft(); // null
Подсказки
Для полного доступа к испытанию нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.