PHP рекурсивный foreach с левой, правой и глубиной

Question

У меня есть файл json, взятый с geonames.org, и я хочу добавить данные из этого файла, используя php recursive foreach .

Мне удалось только, что я просто не понял концепцию левой правой глубины. Глубина сохранена правильно.

Мой код:

public function buildTree($elements, $count = 1, $depth = 0)
    {
        if (isset($elements->geonames)) {
            foreach ($elements->geonames as $element) {
                $left = $count++;

                $elementDB = new \App\Geo();

                $elementDB->id        = $element->geonameId;
                $elementDB->parent_id  = NULL;
                $elementDB->left      = $left;
                $elementDB->right     = $right;
                $elementDB->depth     = $depth;
                $elementDB->name      = $element->name;
                $elementDB->country   = $element->countryCode;
                $elementDB->level     = $element->fcode;
                $elementDB->lat       = $element->lat;
                $elementDB->long      = $element->lng;
                $elementDB->save();

                $elements = $this->getList($element->geonameId, 'element');

                if ($depth < 1) {
                    $this->buildTree($elements, $count, $depth + 1);
                }

                $right = $count++;

                echo "Added element " . $element->name . "\n";
            }
        }
    }

Это должно произойти

Answer 1

Возможная реализация алгоритма поиска в двоичном дереве поиска выглядит следующим образом:

function buildTree($elements, $left, $right, $needle){
    if ($left > $right) return null;
    $middle = floor(($left + $right) / 2);
    $val = $elements[$middle];
    if ($val === $needle) return $val;
    else if ($val < $needle) return buildTree($elements, $left + 1, $right, $needle);
    else if ($val > $needle) return buildTree($elements, $left, $right + 1, $needle);
}

echo buildTree([1, 2, 3, 4, 5], 0, 5, 4);

Вам просто нужно адаптировать это к вашей проблеме

Answer 2

Кажется, вы хотите понять, как это работает? Вы используете рекурсию для обработки каждого элемента. Переменная $ elements - это дерево (или поддерево) с узлами. Ваш код должен просматривать ваше дерево слева направо. На каждой итерации вы проверяете, есть ли у $ elements узлы. Если $ elements имеет (это может быть упорядоченный массив или структура с полями), вы должны обработать эти узлы. Во время каждой проверки вы обнаруживаете каждый узел, есть ли у него другие дочерние узлы или нет. Когда вы найдете первый (назовем его «A») узел, который имеет другие дочерние узлы, вы должны перейти к следующей итерационной рекурсии для обработки дочерних узлов текущего дочернего узла («A»).

Числа представляют порядок, в котором осуществляется доступ к узлам в алгоритме глубины слева-справа.

Честно говоря, я не понимаю, что вы добавили:

$this->buildTree($elements, $count, $depth + 1);

Плохое назначение стиля для переменной в foreach :

Может быть, вам будет интересно Когда целесообразно использовать поиск в глубину (DFS) по сравнению с поиском в ширину (BFS)?

Answer 3

Я предполагаю, что здесь вы создаете двоичное дерево поиска. По сути, дерево - это граф с корнем, «правильными» узлами и листьями.

Вверху всегда один единственный корень, который является конкретным узлом.

Листья не имеют других узлов внизу, они являются "концами" дерева.

Обычные узлы имеют, возможно, двух дочерних элементов, один поменьше (слева) и один побольше (справа). Это делает что-то вроде этого:

Как видите, все узлы, идущие от левого потомка корня, меньше 8. Все дочерние узлы справа больше 8. Таким образом, когда вы ищете «10», вы сразу же знаете, что у вас есть чтобы пройти через правого потомка корня, не нужно исследовать левую сторону (это означает меньше времени обработки).