Binärbaum-Algorithmus in PHP und FAQs

Mit der kontinuierlichen Weiterentwicklung der Webentwicklung, PHP als weit verbreitete Server-Skriptsprache, werden seine Algorithmen und Datenstrukturen immer wichtiger. Unter diesen Algorithmen und Datenstrukturen ist der Binärbaumalgorithmus ein sehr wichtiges Konzept. In diesem Artikel werden der Binärbaumalgorithmus und seine Anwendungen in PHP vorgestellt und Antworten auf häufig gestellte Fragen gegeben.

Was ist ein Binärbaum?

Ein Binärbaum ist eine Baumstruktur, in der jeder Knoten höchstens zwei untergeordnete Knoten hat, nämlich den linken untergeordneten Knoten und den rechten untergeordneten Knoten. Wenn ein Knoten keine untergeordneten Knoten hat, wird er als Blattknoten bezeichnet. Binärbäume werden häufig in Such- und Sortieralgorithmen verwendet.

In PHP können Sie Klassen verwenden, um Binärbäume zu implementieren. Das Folgende ist ein Beispiel für eine binäre Baumknotenklasse:

class TreeNode {
  public $val;
  public $left;
  public $right;

  function __construct($val) {
    $this->val = $val;
    $this->left = null;
    $this->right = null;
  }
}

In dieser TreeNode-Klasse stellt $val den Wert des Knotens dar, $left und $right repräsentieren den linken untergeordneten Knoten bzw. den rechten untergeordneten Knoten des Knotens.

Wie erstellt man einen Binärbaum?

In PHP können Sie einen einfachen Binärbaum mit dem folgenden Code erstellen:

$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);

Dadurch wird ein Binärbaum erstellt, dessen Wurzelknoten den Wert 1 hat, dessen linkes Kind den Wert 2 hat und dessen rechtes Kind den Wert a hat Wert von 3. Der Wert des linken untergeordneten Knotens seines linken untergeordneten Knotens ist 4, und der Wert des rechten untergeordneten Knotens seines linken untergeordneten Knotens ist 5.

Wie durchläuft man einen Binärbaum?

Normalerweise gibt es drei Möglichkeiten, einen Binärbaum zu durchlaufen: Durchquerung vor der Bestellung, Durchquerung nach der Bestellung und Durchquerung nach der Bestellung.

Vorbestellungsdurchquerung bezieht sich darauf, zuerst den Wurzelknoten zu besuchen und dann den linken Teilbaum und den rechten Teilbaum zu durchqueren. In PHP kann die Durchquerung vor der Bestellung durch den folgenden Code implementiert werden:

function preorderTraversal($root) {
  if ($root == null) {
    return;
  }
  echo $root->val . " ";
  preorderTraversal($root->left);
  preorderTraversal($root->right);
}

Durchquerung in der Reihenfolge bedeutet, zuerst den linken Teilbaum zu durchqueren, dann den Wurzelknoten zu besuchen und schließlich den rechten Teilbaum zu durchqueren. In PHP kann die Durchquerung in der Reihenfolge durch den folgenden Code erreicht werden:

function inorderTraversal($root) {
  if ($root == null) {
    return;
  }
  inorderTraversal($root->left);
  echo $root->val . " ";
  inorderTraversal($root->right);
}

Durchquerung nach der Reihenfolge bedeutet, zuerst den linken Teilbaum und den rechten Teilbaum zu durchqueren und dann den Wurzelknoten zu besuchen. In PHP kann die Durchquerung nach der Bestellung durch den folgenden Code erreicht werden:

function postorderTraversal($root) {
  if ($root == null) {
    return;
  }
  postorderTraversal($root->left);
  postorderTraversal($root->right);
  echo $root->val . " ";
}

Wie finde ich Knoten in einem Binärbaum?

Um Knoten in einem Binärbaum zu finden, können Sie einen rekursiven Algorithmus verwenden. Hier ist ein Beispielcode:

function search($root, $val) {
  if ($root == null || $root->val == $val) {
    return $root;
  }
  if ($val < $root->val) {
    return search($root->left, $val);
  }
  return search($root->right, $val);
}

Wenn in diesem Code der Wert des Knotens gleich $val ist, wird der Knoten zurückgegeben. Andernfalls, wenn $val kleiner als der Wert des Knotens ist, suchen Sie im linken Teilbaum. Andernfalls suchen Sie im rechten Teilbaum.

Wie füge ich einen Knoten in einen Binärbaum ein?

Um einen Knoten in einen Binärbaum einzufügen, können Sie einen rekursiven Algorithmus verwenden. Hier ist ein Beispielcode:

function insert($root, $val) {
  if ($root == null) {
    return new TreeNode($val);
  }
  if ($val < $root->val) {
    $root->left = insert($root->left, $val);
  } else {
    $root->right = insert($root->right, $val);
  }
  return $root;
}

Wenn in diesem Code der Binärbaum leer ist, wird ein neuer Knoten zurückgegeben. Andernfalls, wenn $val kleiner als der Wert des Knotens ist, fügen Sie es in den linken Teilbaum ein. Andernfalls in den rechten Teilbaum einfügen.

Wie lösche ich Knoten im Binärbaum?

Um einen Knoten in einem Binärbaum zu löschen, müssen Sie die folgenden drei Situationen berücksichtigen:

1. Der zu löschende Knoten hat keine untergeordneten Knoten, Sie müssen den Knoten nur direkt löschen.
2. Der zu löschende Knoten verfügt über einen untergeordneten Knoten, der zum Ersetzen des Knotens verwendet werden muss.
3. Der zu löschende Knoten hat zwei untergeordnete Knoten. Sie müssen den Nachfolgerknoten des Knotens finden (dh den kleinsten Knoten im rechten Teilbaum des Knotens), den Knoten durch den Nachfolgerknoten ersetzen und ihn dann löschen Nachfolgeknoten.

Das Folgende ist ein Beispielcode:

function deleteNode($root, $val) {
  if ($root == null) {
    return null;
  }
  if ($val < $root->val) {
    $root->left = deleteNode($root->left, $val);
  } else if ($val > $root->val) {
    $root->right = deleteNode($root->right, $val);
  } else {
    if ($root->left == null) {
      return $root->right;
    } else if ($root->right == null) {
      return $root->left;
    }
    $successor = $root->right;
    while ($successor->left != null) {
      $successor = $successor->left;
    }
    $root->val = $successor->val;
    $root->right = deleteNode($root->right, $successor->val);
  }
  return $root;
}

Fazit

Der Binärbaumalgorithmus ist ein sehr wichtiges Konzept in PHP. Durch rekursive Algorithmen können verschiedene Funktionen wie Binärbaumkonstruktion, Durchquerung, Knotensuche, Knoteneinfügung und Knotenlöschung realisiert werden. Das Verständnis dieser Anwendungen ist für die Entwicklung effizienter Webanwendungen sehr hilfreich.

Das obige ist der detaillierte Inhalt vonBinärbaum-Algorithmus in PHP und FAQs. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!