PHP는 선주문, 순차 및 후순 순회 이진 트리 연산 예제를 구현합니다.

이 글에서는 비재귀적 알고리즘을 기반으로 이진 트리에 대한 선순, 순차 및 후순 순회 연산을 구현하는 PHP를 주로 소개합니다. 예제를 기반으로 한 이진 트리의 순차 및 후순 순회 작업이 필요한 친구는 구현 기술을 참조하여 모든 사람에게 도움이 되기를 바랍니다.

개요:

이진 트리 탐색의 원리는 다음과 같습니다.

위 그림에 표시된 이진 트리 탐색의 경우:

1 선주문 탐색: 루트 노드를 먼저 탐색한 다음 왼쪽 하위 트리를 탐색합니다. , 마지막으로 오른쪽 하위 트리를 탐색합니다.

ABDHECFG

2. 순차 순회: 먼저 왼쪽 하위 트리를 순회한 다음 루트 노드를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다.

HDBEAFCG

3. 사후 순회: 먼저 왼쪽 하위 트리를 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 루트 노드를 순회합니다.

HDEBFGCA

구현 방법:

사전 주문 순회: 스택의 선입후출 기능을 사용하여 먼저 루트 노드를 방문한 다음 오른쪽 하위 트리를 푸시한 다음 왼쪽 하위 트리를 푸시합니다. 이런 식으로 꺼낼 때 왼쪽 하위 트리가 먼저 제거되고 오른쪽 하위 트리가 마지막으로 제거됩니다.

function preorder($root){
 $stack = array();
 array_push($stack, $root);
 while(!empty($stack)){
  $center_node = array_pop($stack);
  echo $center_node->value; // 根节点
  if($center_node->right != null)
   array_push($stack, $center_node->right); // 压入右子树
  if($center_node->left != null)
   array_push($stack, $center_node->left); // 压入左子树
 }
}

순서: 아래에서 위로 순회해야 하므로 왼쪽 하위 트리가 먼저 스택에 푸시되고 루트 노드와 오른쪽 하위 트리가 하나씩 방문됩니다.

function inorder($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->left;
  }
  $center_node = array_pop($stack);
  echo $center_node->value;
  $center_node = $center_node->right;
 }
}

후순: 먼저 루트 노드를 저장한 다음 왼쪽 하위 트리와 오른쪽 하위 트리를 순서대로 저장합니다. 그런 다음 출력하십시오.

function tailorder($root){
 $stack = array();
 $outstack = array();
 array_push($$stack, $root);
 while($empty($stack)){
  $center_node = array_pop($stack);
  array_push($outstack, $center_node);
  if($center_node->right != null)
   array_push($stack, $center_node->right);
  if($center_node->left != null)
   array_push($stack, $center_node->left);
 }
 while($empty($outstack)){
  $center_node = array_pop($outstack);
  echo $center_node->value;
 }
}

관련 권장 사항:

PHP를 사용하여 이진 트리가 대칭인지 확인하는 방법

위 내용은 PHP는 선주문, 순차 및 후순 순회 이진 트리 연산 예제를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!