이진 트리 탐색 알고리즘 데모의 PHP 구현

이 글은 주로 PHP로 구현된 이진 트리 순회 알고리즘을 소개하고, PHP의 일반적인 이진 트리에 대한 선순, 중순, 후순 순회 알고리즘 구현 기술을 구체적인 예의 형태로 분석하여 도움이 필요한 친구들이 참고할 수 있습니다.

이 문서의 예에서는 PHP에서 구현된 이진 트리 탐색 알고리즘을 설명합니다. 참고를 위해 모두와 공유합니다. 자세한 내용은 다음과 같습니다.

오늘은 PHP를 사용하여 이진 트리 탐색을 구현했습니다.

생성된 이진 트리는 아래와 같습니다

php 코드는 다음과 같습니다.

<?php
class Node {
  public $value;
  public $child_left;
  public $child_right;
}
final class Ergodic {
  //前序遍历:先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先遍历根节点，然后访问左子树，最后遍历右子树
  public static function preOrder($root){
    $stack = array();
    array_push($stack, $root);
    while(!empty($stack)){
      $center_node = array_pop($stack);
      echo $center_node->value . &#39; &#39;;
      //先把右子树节点入栈，以确保左子树节点先出栈
      if($center_node->child_right != null) array_push($stack, $center_node->child_right);
      if($center_node->child_left != null) array_push($stack, $center_node->child_left);
    }
  }
  //中序遍历:先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树
  public static function midOrder($root){
    $stack = array();
    $center_node = $root;
    while (!empty($stack) || $center_node != null) {
      while ($center_node != null) {
        array_push($stack, $center_node);
        $center_node = $center_node->child_left;
      }
      $center_node = array_pop($stack);
      echo $center_node->value . &#39; &#39;;
      $center_node = $center_node->child_right;
    }
  }
  //后序遍历:先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点
  public static function endOrder($root){
    $push_stack = array();
    $visit_stack = array();
    array_push($push_stack, $root);
    while (!empty($push_stack)) {
      $center_node = array_pop($push_stack);
      array_push($visit_stack, $center_node);
      //左子树节点先入$pushstack的栈，确保在$visitstack中先出栈
      if ($center_node->child_left != null) array_push($push_stack, $center_node->child_left);
      if ($center_node->child_right != null) array_push($push_stack, $center_node->child_right);
    }
    while (!empty($visit_stack)) {
      $center_node = array_pop($visit_stack);
      echo $center_node->value . &#39; &#39;;
    }
  }
}
//创建二叉树
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();
$h = new Node();
$i = new Node();
$a->value = &#39;A&#39;;
$b->value = &#39;B&#39;;
$c->value = &#39;C&#39;;
$d->value = &#39;D&#39;;
$e->value = &#39;E&#39;;
$f->value = &#39;F&#39;;
$g->value = &#39;G&#39;;
$h->value = &#39;H&#39;;
$i->value = &#39;I&#39;;
$a->child_left = $b;
$a->child_right = $c;
$b->child_left = $d;
$b->child_right = $g;
$c->child_left = $e;
$c->child_right = $f;
$d->child_left = $h;
$d->child_right = $i;
//前序遍历
Ergodic::preOrder($a); //结果是：A B D H I G C E F
echo &#39;<br/>&#39;;
//中序遍历
Ergodic::midOrder($a); //结果是： H D I B G A E C F
echo &#39;<br/>&#39;;
//后序遍历
Ergodic::endOrder($a); //结果是: H I D G B E F C A

위 내용은 이진 트리 탐색 알고리즘 데모의 PHP 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!