Binärbaum Bzw. Turnierbaum

rey · 21.07.2010

Hi,
ich möchte einen Turnierbaum erstellen welche anhand von einer dynamisch eingegebenen Zahl mir alle Tabellen Zeilen erstellt.
Sobald die Sieger bekannt sind sollen diese wieder weiter zusammengefasst werden.
Bis eben nur noch einer vorhanden ist.
Dabei ist mir aufgefallen, dass es ja eigentlich nicht anderes als ein Binärbaum ist welche von und bis zu Wurzel gehen soll.
Daher wollte ich eben erst einen Binärbaum erstellen und anschließend die Datensätze etc welche aus einer DB kommen eintragen lassen.
Mein nicht all zu erfolgreicher Ansatz war dieser:

Code:

<?php
echo "<table width=100%>";
function CreatBinaryTree($arr,$num,$beg="",$end="")
{
	$beg;
	$next_num = $num/2;

	for($i = 0; $i <$num; $i++)
	{	
		echo "<tr><td width=100 style=\"border-bottom:#000 1px solid;\">".$arr[$i]."</td><td  style=\"border-bottom:#000 1px solid;\">1:3</td></tr>";
		
	}	

	
	if($next_num==1)
	{
		echo "letzte Zahl ist is=".$arr[0];	
	}else{
		echo $next_num;
		$beg = 
	CreatBinaryTree($arr,$next_num,$beg,$end);
/*	for($i = 0; $i <$next_num; $i++)
	{	
		echo "<tr><td width=100 style=\"border-bottom:#000 1px solid;\">".$arr[$i]."</td><td  style=\"border-bottom:#000 1px solid;\">1:3</td></tr>";
	}	*/
	}
	$end;
	
}




$array = array(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16);
$size = sizeof($array);
CreatBinaryTree($array,$size);
?>
</table>

Duddle · 21.07.2010

AW: Binärbaum Bzw. Turnierbaum

Bitte formuliere nochmal deine Anforderungen, deinen Lösungsansatz und deine Probleme damit neu.
Zum Beispiel die Aussage "ich möchte einen Turnierbaum erstellen welche anhand von einer dynamisch eingegebenen Zahl mir alle Tabellen Zeilen erstellt." Welche Zahl ist gemeint? Wie soll die Tabelle aussehen? Kannst du ein Beispiel nennen?

Duddle

rey · 21.07.2010

AW: Binärbaum Bzw. Turnierbaum

Also mit der Eingabe von dynamischen Zahlen mein ich z.B. wenn ich die Zahl 16 eintrage das ich 16 Zeilen haben möchte, so zu sagen das 8tel Finale
http://www.wcg.com/6th/tournament/2008/tm_match_single_2008up.asp?sort=G080416100
Nach dessen Abschluss werden die nächsten Äste gezeichnet da die Hälfte weg fällt sind wir nun im Viertelfinale etc... bis eben zum Finale
Ich weiß das ich mit einer Datenbank arbeiten werden muss. Mit dieser möglichen Problematik, wollte ich mich aber erst beschäftigen, wenn ich mit den minimal Anforderung fertig bin.
Daher nutze ich auch gerade den Array mit 16 Einträgen.
Meine Idee der Umsetzung war es ich rufe eine Funktion auf, welcher ich eben die Array Inhalte schicke und die Größe des Arrays. An der Größe wird dann die Zahl für den ersten abschnitt des KO-Systems errechnet. Diese teile ich dann durch 2 womit ich auf 8 kommen würde.
Bevor es aber mit dem erstellen der nächsten Blätter weiter geht wollte ich erst noch die eben erstellten Blätter mit Inhalt füllen.
Danach die nächsten leeren Blätter Zeichen.
Wie ich es umsetze diese später mit dem gezielten Inhalt zu füllen weiß ich noch nicht.
Was meine ich mit gewünschten Inhalt?
Nehmen folgendes an:
1.Zeile =>Deutschland
2.Zeile =>England
3.Zeile =>Argentinien
4.Zeile =>Ghana
usw.
Nun gewinnen Deutschland und Ghana
Also sollen die im nächsten Baum Abschnitt gegeneinander antreten.

Mein jetziges Problem ist die Realisierung der Baum Zeichnung denn bei mir werden so wie das Script jetzt ausschaut alle untereinander angezeigt anstatt nebeneinander.

Ich hoffe es ist nun alles Klar.

Duddle · 21.07.2010

AW: Binärbaum Bzw. Turnierbaum

Letztlich ist das ja mehr ein HTML-Layout-Problem, nicht wahr?
Für mich sind das aber tabellarische Daten, deshalb würde ich das ganze auch so ausgeben (auch wenn man sich hier sicher streiten kann, ob das Layouten mit Tabellen ist). Meine Lösung, verallgemeinert von einem Beispiel auf Blatt&Papier, für die Tabelle an sich sieht folgendermaßen aus:

PHP:

<?php
$mannschaften = 8;
$maxEbene = log($mannschaften, 2) + 1;
$gesamtgroesse = 2*$mannschaften - 1;

echo "<table border='1'>";
for($zeile = 0; $zeile < $gesamtgroesse; $zeile++) {
	echo "<tr>";
	for($ebene = 1; $ebene <= $maxEbene; $ebene++) {
		echo "<td>";

		$rest = $zeile % pow(2,$ebene);
		$wunsch = pow(2, $ebene-1)-1;
		echo ($rest == $wunsch) ? "mannschaft" : "&nbsp;";

		echo "</td>";
	}
	echo "</tr>";
}
echo "</table>";
?>

Das erzeugt dir eine Tabelle mit genau $mannschaften vielen Mannschaften mit der entsprechenden Anordnung in Ebenen/Runden.

Wie bin ich dort gelandet?
Auf Karopapier diese Tabelle für ein 8er-Turnier gezeichnet, dort nach den Regeln für die Abstände der Kreuze (bzw. Mannschaftseinträgen in dem Fall) nach oben gesucht, und dabei entsprechend eine kleine Formel gefunden, die in Abhängigkeit von Zeile und Ebene aussagt ob dort eine Mannschaft stehen muss:

Es gibt M Mannschaften. Es gibt daher offensichtlich Emax = ld(M)-1 viele Ebenen/Runden, wobei ld() der Logarithmus Dualis - also Log zur Basis 2 - ist. Die Gesamtgröße G der Tabelle ist 2*M-1 Zeilen. Für Zeile Z (von 0 bis G-1) und Ebene E (von 1 bis Emax) steht eine Mannschaft in diesem Feld, falls folgendes zutrifft:
Z % 2**E == 2**(E-1) - 1
wobei '%' der Modulo-Operator und '**' die Potenzfunktion ist.

Das kannst du anhand eines Beispiels mal nachvollziehen.

Wie du jetzt das ganze mit sinnvollen Daten füllst, oder es schön stylst, das überlasse ich mal dir

Duddle

rey · 21.07.2010

AW: Binärbaum Bzw. Turnierbaum

Vielen Danke!
Jo da einen Style rein zuhauen wird kein Problem.

Ich habe folgendes Problem die Zähle gehen nicht egal wo ich die positioniere.
ich lade die inhalte aus der DB und Speicher diese anschließend in einen Array. Den ruf ich innerhalb der vielen For Schleifen auf.
um die kompletten Elemente auszugeben brauche ich natürlich einen Zähler;
Aus irgendeinem Grund zählt der nicht 0,1,2,3,4,5... sondern überspringt ein paar zahlen.
ich weiß das es an der if($rest == $wunsch) liegt.
Aber ich weiß nicht wie ich das Problem umgehen soll :/
bin schon fleißig bei Google.
sofern mir jemand einen Tipp hat, würde ich mich freuen.

Ich habe es so versucht, dass sobald ich in der if lande der Zaehler um eins hochgezählt wird bei else eins abgezogen wird.
ich bekomme aber solche ausgaben bei dem Zähler

1
-4
-5
-10
-11
-16
-17
.
.
.
-88
-89

ich habe noch mal herum gepfuscht und bekomme nun keine negativen ausgaben mehr aber es wird immer noch falsch gezählt
für die erste ebene klappt der zaehler für die restlich nicht.

PHP:

<?php
require 'mysql_con.php';

function getPlayers($stage,$num,$con)
{
	$Spieler = array();
	
for($i=1; $i<=$num; $i++)
{

		$pstmtt = $con->prepare("SELECT `name` AS playername FROM `player` LEFT JOIN ebene{$stage} ON player.player_id=ebene{$stage}.player_id
		WHERE ebene{$stage}.player_id={$i} group by `player`.`name` LIMIT 1");
		$pstmtt->bind_result($playername);
		$pstmtt->execute();
		$pstmtt->store_result();
		
		while($pstmtt->fetch())
		{
		$Spieler[$i].=$playername;
		}
		
}

//print_r($Spieler);
return $Spieler;
unset($Spieler);
}
/*function storeXY($value)
{	 
	
	$b = array();
	if(sizeof($b)==0)
	{
	$b[] .=$value;
	$r  = $value;
	}
	else{
		$r = end($b);
		$b[] .=$value;
	if($value-$r==2)
	{
		array_pop($b);
		$r = $r+1;
		echo $r;
		array_push($b,$r);
	}
	}
	var_dump($b);
	return $r;
}*/

$mannschaften = 16;
$maxEbene = log($mannschaften, 2) + 1;
$gesamtgroesse = 2*$mannschaften - 1;
$xy=0;
echo "<table width='100%' border='1'>";
	$bla=array();
$ebeneZ=0;
for($zeile = 0; $zeile < $gesamtgroesse; $zeile++) {
    echo "<tr>";
		
    for($ebene = 1; $ebene <= $maxEbene; $ebene++) {
        echo "<td>";
        $rest = $zeile % pow(2,$ebene);
	    $wunsch = pow(2, $ebene-1)-1;

       if($rest == $wunsch) { 
	   //echo "SELECT COUNT(*) AS anzahl FROM ebene{$ebene}";
		
		++$xy;
		if($ebene-$ebeneZ==1)
		{
			$ebeneZ+=1;
			echo $ebeneZ;
			foreach ($bla as $k =>  $wert) {
			   unset($bla[$k]);
			   $bla = array_values($bla);
			   //var_dump($bla);
			}	
		}else{
			}
		if(count($bla)==0){
			$xy;
			array_push($bla,$xy);
			//var_dump($bla);
			echo "Eintrag bei ==0 <br />";
			var_dump($bla);
		}
		else{
			//var_dump($bla);
			echo "Vor Rechnung <br />";
			var_dump($bla);
			//echo sizeof($bla);
			$r = array_pop($bla);
			echo $r;
			//echo "xy = " .$xy;
			if((($xy-$r) == 2)==true)
				{
					var_dump($bla);
					unset($bla[$r]);
					var_dump($bla);
					echo "xy War mit dem Wert ".$xy;
					$erg = $xy-1;
					echo " größer als es sollte daher ist es jetzt";
					$xy=$erg;
					echo  $xy;
					array_push($bla,$xy);
					var_dump($bla);
					
			}else{
				if(in_array($xy,$bla))
				{
					$r = $r +1;
				array_push($bla,$r);
				$xy =$r;
				}
				else{
					$xy=$r;	
				}
			}
			}
		//echo "bla ". $bla;
		$z = getPlayers($ebene,$mannschaften,$con);
		//var_dump($z);
		
		//echo $z[$xy]." XY_WERT: ".$xy;
		echo"xy: ".$xy." ". $z[$xy];
		//echo " erg == ".$erg." mannschaft{$ebene}" ;
		
		}
		else{
			"&nbsp;";
/*			--$xy;
			echo $xy;*/
			//echo $xy;
		}
		
        echo "</td>";
    	
	}
	
    echo "</tr>";
	
}

echo "</table>";

?>

crx_ed9 · 29.07.2010

AW: Binärbaum Bzw. Turnierbaum | Warum {} ??

Moin Großer,

also ich weis zwar nicht obs was zur Sache beiträgt, aber ein Frage habe ich an dich, warum schreibst du die Strings im SQL in {} Klammern ?!

PHP:

$pstmtt = $con->prepare("SELECT `name` AS playername FROM `player` LEFT JOIN ebene{$stage} ON player.player_id=ebene{$stage}.player_id
        WHERE ebene{$stage}.player_id={$i} group by `player`.`name` LIMIT 1");

ist für mich mehr eine Verständnisfrage als eine Lösungsorientierte Frage.

ich für meinen Teil schreibe aus alter Senielheit immer noch alle SQL in diesem Format:

PHP:

$sql= " select * from `myTable` where `myTable`.`playerID`='$var'";

Ja gut es gibt noch die Pascal schreibweise, aber diese hier ist mir neu. Daher sei so gut und erkläre mir einmal wöfür die {} Klammern stehn.
Ich sehe jetzt nicht, dass du zwingend auf ein Array zugreifst, von daher ist für mich die Schreibweise nicht ganz nachvollziehbar.
@edit:
Weiter habe ich festgestellt das die geschweiften Klammern nicht umbedingt funktionell sind. Konnte das Problem aber bis eben nicht genau verifizieren.
Warum es einmal geht und nicht, kann ich aktuell nicht absehen, liegt ggf. daran das ich übermüdet bin.

Versuchs mal mittels norminaler Schreibweise ohne die Klammern, da es ein String in "" ist, solltest du ohne probleme auf die Variabeln zugreifen können.

was man nicht im Kopf hat, hat man auf dem Edit-Button

Also nochwas, stimmen überhaupt die Abfragen und die Ergbnisse der Abfrage ?!

Lass dir die Abfrage mal ausgeben und gib Sie direkt in dein SQL - Datenbank Modul (MySQL oder sonstwas, ggf. auch phpmyadmin) und schau ob das richtige ergebnis dabei rumkommt.
ggf. stimmt dein Baum und die Abfrage nur nicht, oder ich babbel aufgrund der späten / frühen Stund nur noch müll, schließe ich nicht aus, wenns so ist, Entschuldige ich mich in allerform bei dir/euch/allen ..

@end Edit

Vieleicht hilft die Selbstreflektion bei der Problemlösung.

Grüße