首頁 > 後端開發 > php教程 > php 建構二元樹演算法範例程式碼

php 建構二元樹演算法範例程式碼

怪我咯
發布: 2023-03-12 18:18:01
原創
1625 人瀏覽過

本篇主要介紹了PHP建構二元樹演算法範例,小編覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟著小編過來看看吧

樹(Tree)在資料結構還是很重要的,這裡表示二元樹用括號表示法表示。先寫一個二元樹節點類別:

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

  public $lchild = NULL;

  public $rchild = NULL;

  public function construct($data) {
    $this->data = $data;
  }
}
登入後複製

然後建構二元樹:

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;
    }
  }
}
登入後複製

這裡寫上一個列印二元樹的函數(中序遍歷):

function PrintBTNode($node)
{
  if($node != NULL) {
    PrintBTNode($node->lchild);
    echo $node->data;
    PrintBTNode($node->rchild);
  }
}
登入後複製

運行結果:

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

#

以上是php 建構二元樹演算法範例程式碼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板