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))"

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.