이 글에서는 주로 PHP에서 이진 트리의 깊이 우선 순회(선순서, 순차, 후순) 및 너비 우선 순회(레벨) 구현을 소개합니다. 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. 클래스 순회에 모든 순회 방법을 캡슐화했습니다. 2. pre_order2 메소드에서는 스택을 사용할 때 PHP 표준 라이브러리 SPL에서 제공하는 splstack을 사용합니다. 배열 사용에 익숙하신 분들은 array_push()와 array_pop( ) 시뮬레이션 구현. 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;
}说明：level_order2方法中，在使用队列的过程中，我使用的是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）– 然后使用对应的方式 pop 和 push（array_pop()、array_push()
2. 순회:
rrreee
🎜🎜 🎜1. 레벨 탐색: 🎜🎜🎜 🎜rrreee🎜🎜🎜🎜참고: level_order2 메소드에서는 큐를 사용할 때 PHP 표준 라이브러리 SPL에서 제공하는 splqueue를 사용합니다. 배열 사용에 익숙하다면
array_push()를 사용하면 됩니다. 및 array_shift() 시뮬레이션 구현. 🎜🎜🎜🎜사용법: 🎜🎜🎜🎜이제 클라이언트 코드를 살펴보겠습니다. 🎜🎜🎜🎜rrreee🎜🎜🎜🎜🎜🎜보조: 🎜🎜🎜🎜1 클라이언트 Bst에 사용되는 세 가지 클래스. , Avl, Rbt 이전 기사인 "PHP에서 바이너리 트리를 그리는 그래픽 표시 기능에 대한 자세한 설명"을 참조하세요. 🎜🎜2. splstack 및 splqueue를 사용하는 것이 좋습니다. > SPL 표준 라이브러리에 제공되는 코드>? 기사에서 본 내용은 다음과 같습니다. 배열을 사용하여 스택을 설명하는 것처럼 데이터 구조를 설명하기 위해 전통적인 변수 유형을 사용할 수 있지만(Strack) 그에 상응하는 pop 및 push 메서드(array_pop( ))를 사용합니다. >, array_push()), 하지만 조심해야 합니다. 왜냐하면 이는 데이터 구조를 설명하기 위해 특별히 설계되지 않았기 때문입니다. 한 번의 잘못된 작업으로 인해 스택이 파괴될 수 있습니다. SPL의 SplStack 객체는 데이터를 스택 형태로 엄격하게 기술하고 그에 상응하는 메소드를 제공합니다. 동시에 이러한 코드는 배열이 아닌 스택에서 작동한다는 사실도 이해할 수 있어야 하며, 이를 통해 동료는 해당 코드를 더 잘 이해할 수 있고 속도가 더 빨라질 것입니다. 원본 주소: 잃어버린 보석 PHP SPL 🎜🎜🎜3. 이 기사와 관련된 참고 기사: "C 언어의 이진 트리에 대한 일반적인 작업에 대한 자세한 설명 [선순서, 중순서, 후순서, 레벨 순회 및 비재귀 검색, 통계, 비교, 탐색 깊이]", "이진 트리에 대한 깊이 우선 탐색 및 너비 우선 탐색 알고리즘의 Java 구현" 🎜🎜관련 권장 사항: 🎜🎜🎜PHP 정렬 알고리즘 버블 정렬(버블 정렬)🎜🎜🎜🎜🎜🎜🎜🎜 🎜위 내용은 PHP는 이진 트리의 깊이 우선 순회(선주문, 중간 순서, 후순) 및 너비 우선 순회(수준)를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
