Exemple de code d'algorithme de construction d'arbre binaire PHP

Cet article présente principalement des exemples d'algorithmes de construction d'arbres binaires en PHP. L'éditeur pense que c'est plutôt bon. Maintenant, je vais le partager avec vous et le donner comme référence. Suivons l'éditeur et jetons un coup d'œil.

L'arbre est toujours très important dans la structure des données. Ici, l'arbre binaire est représenté par une notation entre parenthèses. Écrivez d'abord une classe de nœuds d'arbre binaire :

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

  public $lchild = NULL;

  public $rchild = NULL;

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

Ensuite, construisez un arbre binaire :

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;
    }
  }
}

Écrivez ici une fonction pour imprimer l'arbre binaire (parcours dans l'ordre) :

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

Résultat de l'exécution :

Entrez une chaîne
"A(B(C,D),G(F))"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!