drzewo binarne - dodawanie wg poziomów Opcje

[megasinski]

Witam
Mam pewien problem
Stworzyłem w mysql tabelę do której chciałbym wstawiać rekordy w pewien określony sposób.
Ma to być hierarchia binarna, czyli drzewko z dwoma odnogami za każdym razem.

tabela posiada kolumny id, id_parent, right, left

Do tabeli mają być dodawane nowe rekordy w taki sposób, aby najpierw, niezależnie od tego jak aktualnie wygląda struktura, rozpoczynając od wybranego rekordu, najpierw sprawdzał pierwszy poziom pod wybranym rekordem i jeśli jest wolne miejsce to w pierwszej kolejności dodawał nowy rekord do prawej odnogi a jeśli ta jest zajęta, to do lewej. Jeśli natomiast w poziomie pierwszym nie ma już miejsca to przechodzi do poziomu drugiego itd.

To co do tej pory wykombinowałem to przynosiło taki efekt, że najpierw sprawdzał prawą odnogę, jeśli była wolna to dopisywał, jeśli nie to sprawdzał lewą i jeśli była wolna to dopisywał, a jeśli nie to wtedy wchodzi w poziom niżej i do tego miejsca było OK, ale dalej kiedy sprawdził rekord w drugim poziomie to juz nie przechodził do następnego rekordu w tym poziomie tylko szedł niżej w będącej już odnodze i praktycznie pomijał pozostałe rekordy w danym poziomie.

Chodzi mi o to, żeby najpierw sprawdził poziom 1 pod jakimś tam rekordem, jeśli jest pełny to wtedy poziom 2, jeśli ten jest pełny to przechodzi do poziomu 3 itd.
Czy da się coś takiego stworzyć w PHP? Jeśli tak to w jaki sposób?
Pomocy please.
Mam nadzieję, że nie zagmatwałem pytania.

[megasinski]

Dzięki wielkie.
Jednak to dało efekt, który już osiągnąłem.
Może spróbuję inaczej to wytłumaczyć.

Powiedzmy, że wyjściowym ID jest 1, który ma pod sobą 2 i 3.
Jeżeli 2 nie ma nic pod sobą, to dodaje kolejne id do niej, czyli np 4.
Potem kolejne id byłoby 5.

To co uzyskałem poprzez Twoją funkcję daje efekt taki, że w dalszej kolejności nie przechodzi do 3, tylko dalej drąży w strukturze 2, czyli sprawdza 4, i nawet nie przechodzi do 5.

A ja chcę uzyskać taki efekt, żeby jeśli okaże się, że 2 ma już zajęte i right i left, to wtedy przechodzi do 3 i sprawdza czy jest pełna czy nie, jeśli tak, to dopiero wtedy przechodzi do 4, a następnie do 5 które to już są na kolejnym poziomie.

Np. na tym rysunku najpierw sprawdza 2, widzi że ona ma zajęte i prawy i lewy, to przechodzi do 3, tam widzi, że prawy jest zajęty , ale lewy wolny więc uzupełnia go numerem ID = 11, następny rekord będzie dodany już w kolejnym poziomie, gdzie sprawdzi 4, potem 5(gdzie doda 12), potem 6(gdzie doda 13) potem 11(lewy pod trójką, gdzie doda 14 i 15), następnie przechodzi niżej i tam wszystkie są puste, więc uzupełnia je po kolei począwszy od prawej.

Oczywiście dodawanie rekordów odbywa się tylko wówczas, kiedy sam chcę dodać kolejny rekord (IMG:style_emoticons/default/cool.gif)

(IMG:http://megas.pl/images/drzewo.jpg)