PHP: Как найти самый левый узел в двоичном дереве? - PullRequest
Новая
       37

PHP: Как найти самый левый узел в двоичном дереве?

0 голосов
/ 16 февраля 2020

Скажите, у меня есть это дерево: 

         root
       /      \
      1        2
    /   \     /
   3     4   5
        /
       6
      /  \
     8    7
    /      \
   9       12
  /
10
  \
  11

Я хочу выбрать root, затем left, результат будет 3. Если right, это будет 2.

Если я выберу 6, то слева будет 10, справа будет 12.

Я был используя это https://packagist.org/packages/kalnoy/nestedset. На данный момент я использую рекурсив сверху вниз для поиска (запрос из базы данных, чтобы найти следующего левого потомка), но это не эффективно, так как дерево станет больше.

Я пытался использовать это (чтобы найти слева): 

if (!$child = self::where('parent_id', $this->id)->where('position', 'left')->first()) {
            return false;
        }

        if (!$grandChild = $child->leftChild()) {
            return $child;
        }

        $outerLeftChild = $child->descendants()->where('position', 'left')->whereIsLeaf()->get();

        if (count($outerLeftChild) <= 0) {
            $outerLeftChild = $child->descendants()->where('position', 'left')->hasChildren()->get();
            if (count($outerLeftChild) <= 0) {
                return $child;
            }
        }

        return $outerLeftChild->sortBy('_lft')->last();

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

У меня есть level, position (влево или вправо) и parent_id для каждого узла данных. Каждый узел будет иметь максимум 2 узла (слева и справа), но он также может иметь один узел или вообще ничего.

Может кто-нибудь хотя бы рассказать мне теорию для этого решения?

...