如何在PHP中構(gòu)造一個二叉樹算法

如何在PHP中構(gòu)造一個二叉樹算法？相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

樹（Tree）在數(shù)據(jù)結(jié)構(gòu)還是很重要的，這里表示二叉樹用括號表示法表示。先寫一個二叉樹節(jié)點類：

// 二叉樹節(jié)點
class BTNode {
  public $data;

  public $lchild = NULL;

  public $rchild = NULL;

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

然后構(gòu)造二叉樹：

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

這里寫上一個打印二叉樹的函數(shù)（中序遍歷）：

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

運行結(jié)果：

輸入一個字符串
"A(B(C,D),G(F))"

看完上述內(nèi)容，你們掌握如何在PHP中構(gòu)造一個二叉樹算法的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！