PHP: Агрегация в двоичном дереве

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

В данном испытании мы будем использовать двоичное дерево, и выполнять агрегацию данных.

src/Node.php

Реализуйте следующие методы в классе:

  • getCount() — возвращает количество узлов в дереве.
  • getSum() — возвращает сумму всех ключей дерева.
  • toArray() — возвращает одномерный массив содержащий все ключи.
  • toString() — возвращает строковое представление дерева.
  • every($fn) — проверяет, удовлетворяют ли все ключи дерева условию, заданному в передаваемой функции.
  • some($fn) - проверяет, удовлетворяет ли какой-либо ключ дерева условию, заданному в передаваемой функции.

При обходе дерева нужно использовать порядок слева-направо. То есть вначале обрабатываем ключ узла, затем ключ левого ребёнка, после чего ключ правого ребёнка.

Примеры

<?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,
            null,
            new Node(23)
        )
    )
);

$tree->getCount(); // 9
$tree->getSum(); // 96
$tree->toArray(); // [9, 4, 3, 6, 5, 7, 17, 22, 23]
$tree->toString(); // '(9, 4, 3, 6, 5, 7, 17, 22, 23)'

$tree->every(fn($key) => $key <= 23); // true
$tree->every(fn($key) => $key < 10); // false
$tree->some(fn($key) => $key < 4); // true
$tree->some(fn($key) => $key > 24); // false

Подсказки

  • Двоичное дерево
  • Для реализации каждого из методов потребуется выполнить обход всех узлов дерева.
  • Вспомните принцип работы метода array_reduce.

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

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

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

Отзывы

Аватар пользователя Константин Кузьмин
Константин Кузьмин 09 мая 2021

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