PHP 는 이 진 트 리 깊이 우선 옮 겨 다 니 기(앞 순서,가운데 순서,뒤 순서)와 너비 우선 옮 겨 다 니 기(차원)인 스 턴 스 상세 설명 을 실현 합 니 다.

본 논문 의 사례 는 PHP 가 이 진 트 리 의 깊이 를 우선적으로 옮 겨 다 니 는 것(앞 순서,중간 순서,뒤 순서)과 넓 은 범위 의 우선 옮 겨 다 니 는 것(차원)을 설명 한다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
선언:
깊이 우선 옮 겨 다 니 기:모든 가능 한 분기 경 로 를 더 이상 깊이 들 어 갈 수 없 을 때 까지 깊이 들 어가 고 모든 노드 는 한 번 만 방문 할 수 있 습 니 다.특히 주의해 야 할 것 은 이 진 트 리 의 깊이 는 우선 옮 겨 다 니 는 것 이 특수 하 므 로 먼저 옮 겨 다 니 거나 중간 에 옮 겨 다 니 거나 뒤 를 옮 겨 다 니 는 것 으로 나 눌 수 있다.구체 적 인 설명 은 다음 과 같다.
앞 순서 옮 겨 다 니 기:뿌리 노드->왼쪽 트 리->오른쪽 트 리
중간 순서:왼쪽 하위 트 리->뿌리 노드->오른쪽 하위 트 리
뒤 순 옮 겨 다 니 기:왼쪽 하위 트 리->오른쪽 하위 트 리->뿌리 노드
넓 은 범위 우선 옮 겨 다 니 기:층 차 를 옮 겨 다 니 는 것 이 라 고도 부 릅 니 다.위 에서 아래로 각 층 을 순서대로 방문 합 니 다.각 층 에서 왼쪽 에서 오른쪽으로(오른쪽 에서 왼쪽으로)결점 을 방문 하고 한 층 을 방문 하면 다음 층 으로 들 어 갑 니 다.결점 이 없 을 때 까지 입 니 다.
예 를 들 어 이 나무 에 대해:

깊이 우선 순위:
이전 순서:10,8,7,9,12,11,13
역순:7,8,9,10,11,12,13
후 순 옮 김:7,9,8,11,13,12,10
우선 범위:
층 차 옮 김:10,8,12,7,9,11,13
이 진 트 리 의 깊이 를 우선 으로 옮 겨 다 니 는 비 재 귀적 인 방법 은 스 택 을 사용 하고 넓 은 범위 에서 우선 옮 겨 다 니 는 비 재 귀적 인 방법 은 대기 열 을 사용 합 니 다.
깊이 우선 순위:
1.앞 순 서 를 옮 겨 다 니 기:

/**
*     (    )
*/
private function pre_order1($root)
{
    if (!is_null($root)) {
      //      __FUNCTION__，       ，             ，         
      $function = __FUNCTION__;
      echo $root->key . " ";
      $this->$function($root->left);
      $this->$function($root->right);
    }
}
/**
*     (     )
*                ，         。          ，     。
*/
private function pre_order2($root)
{
    //    $stack = new splstack();
    //    $stack->push($root);
    //    while(!$stack->isEmpty()){
    //      $node = $stack->pop();
    //      echo $node->key.' ';
    //      if(!is_null($node->right)){
    //        $stack->push($node->right);
    //      }
    //      if(!is_null($node->left)){
    //        $stack->push($node->left);
    //      }
    //    }
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        //              ，        
        $stack->push($node);
        echo $node->key . ' ';
        $node = $node->left;
      }
      $node = $stack->pop();
      $node = $node->right;
    }
}
//    
public function PreOrder()
{
    //       tree           
    //   $this->pre_order1($this->tree->root);
    $this->pre_order2($this->tree->root);
}

설명:1.나 는 모든 옮 겨 다 니 는 방법 을 하나의 traverse 에 봉 했다.2、pre_order 2 방법 에서 스 택 을 사용 하 는 과정 에서 저 는 PHP 표준 라 이브 러 리 SPL 에서 제공 하 는 splstack 을 사 용 했 습 니 다.만약 에 배열 을 사용 하 는 습관 이 있다 면array_push() 과array_pop() 시 뮬 레이 션 을 사용 하여 실현 할 수 있 습 니 다.
2.중간 순서 옮 겨 다 니 기:

/**
*     (    )
*/
private function mid_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      echo $root->key . " ";
      $this->$function($root->right);
    }
}
/**
*     (     )
*                ，         。          ，     。
*/
private function mid_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        $stack->push($node);
        $node = $node->left;
      }
      $node = $stack->pop();
      echo $node->key . ' ';
      $node = $node->right;
    }
}
//    
public function MidOrder()
{
    //    $this->mid_order1($this->tree->root);
    $this->mid_order2($this->tree->root);
}

3.뒤 순서 옮 겨 다 니 기:

/**
*     (    )
*/
private function post_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      $this->$function($root->right);
      echo $root->key . " ";
    }
}
/**
*     (     )
*                ，         。          ，     。
*                       ，        lastVisited           
*/
private function post_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $node = $root;
    $stack = new splstack();
    //            
    $lastVisited = NULL;
    $stack->push($node);
    while(!$stack->isEmpty()){
      $node = $stack->top();//          
      if(($node->left == NULL && $node->right == NULL) || ($node->right == NULL && $lastVisited == $node->left) || ($lastVisited == $node->right)){
        echo $node->key.' ';
        $lastVisited = $node;
        $stack->pop();
      }else{
        if($node->right){
          $stack->push($node->right);
        }
        if($node->left){
          $stack->push($node->left);
        }
      }
    }
}
//    
public function PostOrder()
{
    //    $this->post_order1($this->tree->root);
    $this->post_order2($this->tree->root);
}

우선 범위:
1.차원 옮 겨 다 니 기:

/**
*     (    )
*          ，        
*/
private function level_order1($root,$level){
    if($root == NULL || $level < 1){
      return;
    }
    if($level == 1){
      echo $root->key.' ';
      return;
    }
    if(!is_null($root->left)){
      $this->level_order1($root->left,$level - 1);
    }
    if(!is_null($root->right)){
      $this->level_order1($root->right,$level - 1);
    }
}
/**
*     (     )
*          
              ，        。
*/
private function level_order2($root){
    if(is_null($root)){
      return;
    }
    $node = $root;
    //      
//    $queue = array();
//    array_push($queue,$node);
//
//    while(!is_null($node = array_shift($queue))){
//      echo $node->key.' ';
//      if(!is_null($node->left)){
//        array_push($queue,$node->left);
//      }
//      if(!is_null($node->right)){
//        array_push($queue,$node->right);
//      }
//    }
    $queue = new splqueue();
    $queue->enqueue($node);
    while(!$queue->isEmpty()){
      $node = $queue->dequeue();
      echo $node->key.' ';
      if (!is_null($node->left)) {
        $queue->enqueue($node->left);
      }
      if (!is_null($node->right)) {
        $queue->enqueue($node->right);
      }
    }
}
//    
public function LevelOrder(){
//    $level = $this->getdepth($this->tree->root);
//    for($i = 1;$i <= $level;$i ++){
//      $this->level_order1($this->tree->root,$i);
//    }
    $this->level_order2($this->tree->root);
}
//      
private function getdepth($root){
    if(is_null($root)){
      return 0;
    }
    $left = getdepth($root -> left);
    $right = getdepth($root -> right);
    $depth = ($left > $right ? $left : $right) + 1;
    return $depth;
}

설명:levelorder 2 방법 에서 대기 열 을 사용 하 는 과정 에서 저 는 PHP 표준 라 이브 러 리 SPL 에서 제공 하 는 splqueue 를 사 용 했 습 니 다.만약 에 배열 을 사용 하 는 습관 이 있다 면array_push() 과array_shift() 시 뮬 레이 션 을 사용 하여 실현 할 수 있 습 니 다.
사용:
이제 클 라 이언 트 코드 를 살 펴 보 겠 습 니 다.

class Client
{
  public static function Main()
  {
    try {
      //         
      function autoload($class)
      {
        include strtolower($class) . '.php';
      }
      spl_autoload_register('autoload');
      $arr = array(10, 8, 12, 7, 9, 11, 13);
      $tree = new Bst();
//      $tree = new Avl();
//      $tree = new Rbt();
      $tree->init($arr);
      $traverse = new traverse($tree);
      $traverse->PreOrder();
//      $traverse->MidOrder();
//      $traverse->PostOrder();
//      $traverse->LevelOrder();
    } catch (Exception $e) {
      echo $e->getMessage();
    }
  }
}
CLient::Main();

보충:
1.클 라 이언 트 에서 사용 하 는 세 가지 유형의 Bst,Avl,Rbt 는 앞의 편 을 참고 할 수 있 습 니 다.PHP 는 이 진 트 리 그래 픽 디 스 플레이 기능 에 대한 상세 한 설명 을 구현 합 니 다.
2.왜 SPL 표준 라 이브 러 리 에서 제공 하 는splstack과splqueue를 사용 하 는 것 을 추천 합 니까?이것 은 내 가 어떤 글 에서 본 것 이다.비록 우 리 는 전통 적 인 변수 유형 으로 데이터 구 조 를 묘사 할 수 있 지만,예 를 들 어 스 택(Strack)C 를 배열 로 묘사 한 다음 에 대응 하 는 방식 으로 pop 과 pusharray_pop(),array_push()를 사용 할 수 있 지만,너 는 항상 조심해 야 한다.데이터 구 조 를 설명 하 는 데 사용 되 는 C 가 아니 기 때문에 이 스 택 을 파괴 할 수 있 기 때문이다.반면 SPL 의 SplStack 대상 은 엄 격 히 스 택 형식 으로 데 이 터 를 설명 하고 이에 대응 하 는 방법 을 제공한다.또한 이러한 코드 는 특정한 배열 이 아 닌 스 택 을 조작 하고 있다 는 것 을 이해 하여 동료 들 이 해당 하 는 코드 를 잘 이해 하고 더욱 빠 를 수 있 을 것 입 니 다.원문 주소:PHP SPL,잃 어 버 린 보석
3.본 논문 과 관련 된 참고 글:C 언어 이 진 트 리 에서 흔히 볼 수 있 는 조작 에 대한 상세 한 설명,자바 는 이 진 트 리 의 깊이 우선 스 트 리밍 과 너비 우선 스 트 리밍 알고리즘 예제 를 실현 합 니 다.
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.