비재귀 알고리즘을 기반으로 하는 선순, 순차 및 후순 순회 이진 트리 연산을 구현하는 PHP의 예

이 글에서는 주로 비재귀적 알고리즘을 기반으로 이진 트리에 대한 선순서, 순차 및 후순 순회 작업을 구현하는 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 직렬화 및 역직렬화 원칙에 대한 자세한 설명

설명 Swoole의 WeChat 코드 스캐닝 로그인 기능을 기반으로 코드를 구현하는 과정

위 내용은 비재귀 알고리즘을 기반으로 하는 선순, 순차 및 후순 순회 이진 트리 연산을 구현하는 PHP의 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!