Как реализовать заполнение бинарного дерева в ширину на PHP?

Question

[RiGs]

Добрый день, есть такая задача

дан набор чисел, составить из них двоичное дерево (не ДДП), заполняя его по уровням. Это означает, что первый элемент добавляется на первый уровень, второй и третий – на второй уровень, элементы с четвертого по седьмой – на третий уровень и т.д.

Алгоритм нашел

Как решать эту задачу? Используя очередь.
Первый элемент набора поместим в корень дерева. Поместим этот корень в очередь два раза. Теперь, для каждого следующего элемента набора будем создавать новую вершину, затем вынимать одну вершину из очереди и если у этой вершины нет левого сына, то добавлять созданную вершину как левого сына, если нет правого – то как правого. После этого добавленная вершина дважды добавляется в очередь.
Каждая новая вершина добавляется в очередь дважды, чтобы к ней можно было добавить двух детей: левого и правого.

Попытался написать код, но не пойму как в итоге получить само результирующее дерево?
Вот класс BinaryNode

class BinaryNode
{
    public $value;
    public $left  = NULL;
    public $right = NULL;
 
    public function __construct ($value)
    {
        $this->value = $value;
    }
}

и сама реализация

// Рандомно заполним исходный массив
for ($i=0; $i<10; $i++)
{
    $array[$i] = rand(0, 100);
}
 
// Корень
$node = new BinaryNode($array[0]);
 
// Создадим очередь и добавим 2 раза корень
$queue = new SplQueue();
$queue->enqueue($node);
$queue->enqueue($node);
 
// В цикле перебираем массив и выполняем действия согласно алгоритму
for ($i=1; $i<count($array); $i++)
{
    $t = $queue->dequeue();
    $node = new BinaryNode($array[$i]);
    if($t->left == null)
        $t->left = $node;
    else
        $t->right = $node;
    
    $queue->enqueue($node);
    $queue->enqueue($node);
}

Что нужно добавить, где получить дерево? мне нет необходимости получать двоичное дерево, мне просто необходимо заполнить структуру, такую как двоичное дерево, причем заполнить именно "в ширину". Структура выглядит так Элементы должны быть добавлены в том порядке, как указано на картинке

Answer 1

[ldv]

// Корень
$node = new BinaryNode($array[0]);

$root = $node // в $root сохраняем корневой узел

Comments

[RiGs]

а куда это написать конкретно?

[ldv]

$root = $node; после // Корень
$node = new BinaryNode($array[0]);

[RiGs]

ldvldv: и всё? тут я и получу результирующее дерево? всё остальное верно?

[ldv]

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