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.

[timon27]

Po piersze zrezygnuj z kolumny id_parent, bo jest zbędna i znacznie utrudnia procedury.
Zakładam, że id jest autoincrement.
Piszę od ręki, więc pewnie są błędy, ale chodzi o ideę

[PHP] pobierz, plaintext 
function dodaj($id){
  $r=mysql_query("SELECT * FROM drzewo WHERE id=$id");
 
  $right=mysql_result($r,0,'right');
  if($right!=NULL){//tego nie jestem pewien
     mysql_query("INSERT INTO drzewo VALUES ('',NULL,NULL)");
  }
 
  $left=mysql_result($r,0,'right');
  if($left!=NULL){//tego nie jestem pewien
     mysql_query("INSERT INTO drzewo VALUES ('',NULL,NULL)");
  }
 
  dodaj($right);//drzewo rozrasta się niesymetrycznie, ale o tym już nie było mowy
}
[PHP] pobierz, plaintext 

Ten post edytował timon27 13.09.2013, 20:34:08