Ogólne przechodzenie przez drzewo (nieskończone) w przeszukiwaniu wszerz;

Nadal myślę, ale znacznie szybsze niż przechodzenie przez drzewo byłoby identyfikatorem position_id dla każdej możliwej pozycji. Jeśli spojrzysz na kompletne drzewo pewnego poziomu, zobaczysz, o co mi chodzi – tak wygląda twój przykład.

Połączenia między position i position_id są czymś, co ma prostą arytmetykę int (div i modulo).

Wszystkie węzły w poddrzewach mają niektóre z tych właściwości - na przykład bezpośrednie podwęzły węzła 4 (trzeci węzeł w drugim rzędzie) są liczbami

1 + 5 + (3-1)*5 +   1 
1 + 5 + (3-1)*5 +   2
1 + 5 + (3-1)*5 +   3
1 + 5 + (3-1)*5 +   4
1 + 5 + (3-1)*5 +   5

Więc nadal musiałbyś przemierzać poziomy w pętli, ale nie węzły, jeśli zarządzasz tym numerem pozycji w każdym węźle.

Krok 2:

Wiersz r ma 5^r elementów (zaczynając od wiersza 0).

Przechowuj w każdym węźle wiersz i kolumnę, w każdym wierszu kolumna zaczyna się od 0. Zatem drugi wiersz to nie 2,3,4,5,6, ale 1|0, 1|1, 1|2, 1| 3, 1|4.

Jeśli twój korzeń wyszukiwania to 1|1 (wiersz 1, drugi element, w twoim ładnym drzewie o nazwie "3"), to wszystkie dzieci w wierszu 2 mają

  col / 5 = 1

wszystkie dzieci w rzędzie 3 mają

  col / 25 = 1

i tak dalej.

Jeden poziom poniżej węzła 2|10 to węzły 3|(5*10) do 3|(5*11-1) =50 .. 55-1

dwa poziomy poniżej to węzły 4|(50*5) do 4|(55*5-1)

i tak dalej.

Krok 3

Pseudokod:

getFreeNode($node){
    $rowMax = 100;
    $row   = $node->row + 1;
    $from  = 5 * $node->col;
    $to    = $from + 5;
    while($row <= $rowMax){
        if ($id = query("select id from member " 
            ."where row = $row and col >= $from and col < $bis"
            ." and empty_position > 0"))
        {
            return $id;
        }
        $row++;
        $from *= 5;
        $to *= 5;
    }
}

insertNode($parent, $node){
    $node->row = $parent->row + 1;
    $node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
    $node->parent_id = $parent->member_id
}

Zapytaj, czy potrzeba więcej szczegółów.