Binären Baum dynamisch in HTML darstellen

[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