Binären Baum dynamisch in HTML darstellen

[Joachim B.]

Hallo *,

ich finde einfach keine Lösung zu meinem Problem und alles selbst aufzubauen bekomme ich leider auch noch nicht perfekt hin.

Ich habe ein PHP-Objekt welches zwei Knoten Attribute hat, welche vom gleichen Typ der Klasse sind. Sodass ich einen Binärbaum habe.

Diese wollte ich jetzt am liebsten in einer html-table darstellen Beispiel siehe hier:

...............Parent............
......Child1..........Child2.....
.Enkel11.Enkel12.Enkel21.Enkel22.

oder auf sodass die Spalten als Ebene für die Blätter dienen, was bei größen Bäumen definitiv von Vorteil wäre.

Das Vater-Element hat immer eine andere Tiefe und kann ca. 8 Ebenen an Kindern haben. Diese kann ich mir aber ausgeben lassen.

Hatte jemand schon das gleiche Problem oder kennt eine Libary die einem soetwas erstellen kann?

Dazu muss ich sagen, dass ich nicht in diesem Muster das darstellen möchte:

P
|C
||C
|C
||C
|||C
|||C

Vielen dank für eure Hilfe.

[Christian Seiler]

Hallo,

Ich habe ein PHP-Objekt welches zwei Knoten Attribute hat, welche vom gleichen Typ der Klasse sind. Sodass ich einen Binärbaum habe.

Diese wollte ich jetzt am liebsten in einer html-table darstellen Beispiel siehe hier:

...............Parent............
......Child1..........Child2.....
.Enkel11.Enkel12.Enkel21.Enkel22.

Folgendes habe ich mal schnell zusammengehackt (HTML-Ausgabe ist deswegen sehr unschön!), um zu demonstrieren, wie so etwas grundsätzlich funktionieren könnte (behandelt auch den Fall korrekt, dass der Baum nicht ausgeglichen ist):

<?php  
  
class Node {  
  public $left;  
  public $right;  
  public $payload;  
}  
  
// Tiefe eines Baumes bestimmen  
function getDepth ($node) {  
  if ($node === null) return -1;  
  return max (getDepth ($node->left), getDepth ($node->right)) + 1;  
}  
  
// Breite (in Pixel)  
$cellWidth = '70';  
// Baum erstellen  
$tree = new Node;  
$tree->payload = 'Root';  
$tree->left = new Node;  
$tree->left->payload = 'Left';  
$tree->left->left = new Node;  
$tree->left->left->payload = 'Left Left';  
$tree->left->right = new Node;  
$tree->left->right->payload = 'Left Right';  
$tree->right = new Node;  
$tree->right->payload = 'Right';  
$tree->right->right = new Node;  
$tree->right->right->payload = 'Right Right';  
$tree->right->right->left = new Node;  
$tree->right->right->left->payload = 'Right Right Left';  
$tree->right->right->right = new Node;  
$tree->right->right->right->payload = 'Right Right Right';  
  
$depth = getDepth ($tree);  
  
$levelNodes = array ($tree);  
  
echo "<table style=\"empty-cells: show;\" border=\"1\">\n";  
  
for ($i = 0; $i <= $depth; $i++) {  
  $newLevelNodes = array ();  
  
  $span = pow (2, $depth - $i);  
  $width = $cellWidth * $span;  
  
  echo '<tr>';  
  
  foreach ($levelNodes as $node) {  
    if ($node === null) {  
      echo '<td colspan="'.$span.'" style="width: '.$width.'px; text-align: center;"></td>';  
      $newLevelNodes[] = null;  
      $newLevelNodes[] = null;  
    } else {  
      echo '<td colspan="'.$span.'" style="width: '.$width.'px; text-align: center;">'.htmlspecialchars($node->payload).'</td>';  
      $newLevelNodes[] = $node->left;  
      $newLevelNodes[] = $node->right;  
    }  
  }  
  
  echo "</tr>\n";  
  
  $levelNodes = $newLevelNodes;  
}  
  
echo "</table>\n";

Ich hoffe, die grundlegende Idee wird klar. Der Algorithmus liegt übrigens in der Laufzeitklasse [latex]O(n + n\log n) = O(n\log n)[/latex], wenn mich nicht alles täuscht.

Viele Grüße,
Christian

[Christian Seiler]

Hallo,

Der Algorithmus liegt übrigens in der Laufzeitklasse [latex]O(n + n\log n) = O(n\log n)[/latex], wenn mich nicht alles täuscht.

Ok, nochmal drüber nachgedacht: Das stimmt nur, wenn der Baum balanciert ist. Wenn er komplett unbalanciert ist (d.h. eine verkettete Liste), dann sieht's schlechter aus...

Viele Grüße,
Christian

[Christian Seiler]

Hallo nochmal,

Der Algorithmus liegt übrigens in der Laufzeitklasse [latex]O(n + n\log n) = O(n\log n)[/latex], wenn mich nicht alles täuscht.

Ok, nochmal drüber nachgedacht: Das stimmt nur, wenn der Baum balanciert ist. Wenn er komplett unbalanciert ist (d.h. eine verkettete Liste), dann sieht's schlechter aus...

Ok, jetzt aber nochmal richtig: Wenn der Baum komplett balanciert ist und es genau [latex]n = 2^k - 1, k \in \mathbb{N}[/latex] Elemente im Baum gibt (best case), dann ist die Laufzeitklasse sogar nur [latex]O(2n + 1 + n) = O(n)[/latex]. Wenn der Baum überhaupt nicht balanciert ist (verkettete Liste), dann ist die Laufzeitklasse dagegen [latex]O(2n + 1 + 2^n + 1) = O(2^n)[/latex]. Alles andere liegt irgendwo dazwischen.

Viele Grüße,
Christian

[Joachim B.]

Ich hoffe, die grundlegende Idee wird klar. Der Algorithmus liegt übrigens in der Laufzeitklasse [latex]O(n + n\log n) = O(n\log n)[/latex], wenn mich nicht alles täuscht.

Vielen Dank Christian,
das wird mir aufjedenfall weiterhelfen können und der Aufwand kann mir zur Zeit noch schnuppe sein, da es bei meinen Bäumen kaum zu einem kommt, dessen Tiefe > 8 ist.

Auch Danke an EKKI für die Listen-Variante.

Gruß
Joachim

[EKKi]

Mahlzeit Joachim B.,

Dazu muss ich sagen, dass ich nicht in diesem Muster das darstellen möchte:

P
|C
||C
|C
||C
|||C
|||C

Aber gerade für derartige Bäume (jeweilige Kind-Anzahl immer gleich bzw. vorhersehbar) bieten sich doch entsprechend formatierte Listen geradezu an ... ich habe da mal eben auf die Schnelle was zusammengeklimpert (müsstest Du hier und da Deinen Vorstellungen entsprechend anpassen):

<style type="text/css">[code lang=css]  
  
ul.tree,  
ul.tree li,  
ul.tree ul {  
  margin:   0;  
  padding:  0;  
}  
  
ul.tree li {  
  display:  inline;  
  float:    left;  
}  
  
ul.tree div {  
  display:          inline-block;  
  margin:           2px;  
  width:            100%;  
  border:           1px outset blue;  
  text-align:       center;  
}

</style>

<ul class="tree">
  <li>
    <div>Eltern</div>
    <ul>
      <li>
        <div>Kind 1</div>
        <ul>
          <li>
            <div>Enkel 1</div>
            <ul>
              <li>
                <div>Urenkel 1</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
              <li>
                <div>Urenkel 2</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
            </ul>
          </li>
          <li>
            <div>Enkel 2</div>
            <ul>
              <li>
                <div>Urenkel 1</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
              <li>
                <div>Urenkel 2</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
            </ul>
          </li>
        </ul>
      </li>
      <li>
        <div>Kind 2</div>
        <ul>
          <li>
            <div>Enkel 1</div>
            <ul>
              <li>
                <div>Urenkel 1</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
              <li>
                <div>Urenkel 2</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
            </ul>
          </li>
          <li>
            <div>Enkel 2</div>
            <ul>
              <li>
                <div>Urenkel 1</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
              <li>
                <div>Urenkel 2</div>
                <ul>
                  <li><div>...</div></li>
                  <li><div>...</div></li>
                </ul>
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>[/code]

Der PHP-Code, der diese Struktur erstellt, sollte recht einfach zu stricken sein ...

MfG,
EKKi