Beispielcode für den PHP-Binärbaumkonstruktionsalgorithmus

Dieser Artikel stellt hauptsächlich Beispiele für Binärbaumkonstruktionsalgorithmen in PHP vor. Jetzt werde ich ihn mit Ihnen teilen und als Referenz geben. Folgen wir dem Editor und werfen wir einen Blick darauf.

Der Baum ist in der Datenstruktur immer noch sehr wichtig. Hier wird der Binärbaum durch Klammernotation dargestellt. Schreiben Sie zuerst eine Binärbaumknotenklasse:

// 二叉树节点
class BTNode {
  public $data;

  public $lchild = NULL;

  public $rchild = NULL;

  public function construct($data) {
    $this->data = $data;
  }
}

Dann erstellen Sie einen Binärbaum:

function CreateBTNode(&$root,string $str)
{
  $strArr = str_split($str);
  $stack = [];
  $p = NULL; // 指针
  $top = -1;
  $k = $j = 0;
  $root = NULL;
  foreach ($strArr as $ch) {
    switch ($ch) {
      case '(':
        $top++;
        array_push($stack, $p);
        $k = 1;
        break;
      case ')':
        array_pop($stack);
        break;
      case ',':
        $k = 2;
        break;
      default:
        $p = new BTNode($ch);
        if($root == NULL) {
          $root = $p;
        } else {
          switch ($k) {
            case 1:
              end($stack)->lchild = $p;
              break;
            case 2:
              end($stack)->rchild = $p;
              break;
          }
        }
        break;
    }
  }
}

Schreiben Sie hier eine Funktion zum Drucken des Binärbaums (Durchquerung in der richtigen Reihenfolge):

function PrintBTNode($node)
{
  if($node != NULL) {
    PrintBTNode($node->lchild);
    echo $node->data;
    PrintBTNode($node->rchild);
  }
}

Ergebnis ausführen:

Geben Sie eine Zeichenfolge ein
"A(B(C,D),G(F))"

Das obige ist der detaillierte Inhalt vonBeispielcode für den PHP-Binärbaumkonstruktionsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!