How to implement binary tree algorithm in PHP

This article mainly introduces the method of constructing a binary tree algorithm in PHP. Interested friends can refer to it. I hope it will be helpful to everyone.

Tree is still very important in the data structure. Here, the binary tree is represented by bracket notation. First write a binary tree node class:

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

  public $lchild = NULL;

  public $rchild = NULL;

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

Then construct the binary tree:

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

here Write a function that prints a binary tree (in-order traversal):

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

Running result:

Enter a string
"A(B(C,D),G(F))"

The above is the entire content of this article, I hope it will be helpful to everyone's study.

Related recommendations:

php constructionBinary tree algorithmSample code

python implementationBinary tree algorithmand kmp algorithm example

PHP implementation of KMP algorithm

The above is the detailed content of How to implement binary tree algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!