Comment implémenter l'algorithme d'arbre binaire en PHP

Cet article présente principalement la méthode de construction d'un algorithme d'arbre binaire en PHP. Les amis intéressés peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

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 l'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 qui imprime un arbre binaire (parcours dans l'ordre) :

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

Résultat d'exécution :

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

Ce qui précède est tout le contenu de ce article, j'espère que cela aidera tout le monde à apprendre Helps.

Recommandations associées :

Construction phpAlgorithme d'arbre binaireExemple de code

Algorithme d'arbre binaire et exemples d'algorithmes kmp implémentés en python

Algorithme KMP implémenté en PHP

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!