Maison >développement back-end >tutoriel php >Explication détaillée des étapes de l'algorithme de première traversée en profondeur et en largeur de l'arbre binaire en PHP
Cette fois, je vais vous apporter une explication détaillée des étapes de l'algorithme pour implémenter le parcours en profondeur et en largeur des arbres binaires en PHP. Quelles sont les précautions pour implémenter le parcours en profondeur et en largeur des arbres binaires. Trees en PHP.Voici des cas pratiques.
Avant-propos :
Traversée en profondeur : explorez en profondeur tous les chemins de branchement possibles jusqu'à ce qu'ils ne puissent plus aller plus profond. Et chaque nœud ne peut être visité qu’une seule fois. Il est important de noter que le parcours en profondeur d'abord des arbres binaires est spécial et peut être subdivisé en parcours pré-ordre, parcours dans l'ordre et parcours post-ordre. Les instructions spécifiques sont les suivantes :
Parcours en précommande : nœud racine->sous-arbre gauche->sous-arbre droit
Parcours dans l'ordre : sous-arbre gauche->nœud racine->sous-arbre droit
Parcours post-ordre : sous-arbre gauche->sous-arbre droit->nœud racine
Parcours en largeur d'abord : également appelé parcours hiérarchique, chaque couche est séquencée de haut en bas Accédez, dans chaque couche, aux nœuds d'accès de gauche à droite (ou de droite à gauche). Après avoir accédé à une couche, entrez dans la couche suivante jusqu'à ce qu'aucun nœud ne soit accessible.
Par exemple, pour cet arbre :
Parcours en profondeur :
Parcours en précommande : 10 8 7 9 12 11 13
Parcours dans l'ordre : 7 8 9 10 11 12 13
Parcours post-ordre : 7 9 8 11 13 12 10
Parcours en largeur d'abord :
Parcours de niveau : 10 8 12 7 9 11 13
La méthode non récursive courante pour le parcours en profondeur d'un arbre binaire consiste à utiliser une pile, et la méthode courante pour le parcours non récursif en largeur consiste à utiliser une file d'attente.
Parcours en profondeur d'abord :
1. Parcours de précommande :
/**
* 前序遍历(递归方法)
*/
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);
}Explication : 1. Je vais Le Les méthodes de parcours sont encapsulées dans un parcours de classe. 2. Dans la méthode pre_order2, lors de l'utilisation de la pile, j'utilise splstack fourni par la bibliothèque standard PHP SPL. Si vous avez l'habitude d'utiliser des tableaux, vous pouvez utiliser <a href="http://www.php.%20cn/wiki/1001.html" target="_blank">array_push<code><a href="//m.sbmmt.com/wiki/1001.html" target="_blank">array_push</a>() () et array_pop() implémentation de simulation.
2. Parcours dans l'ordre :
/**
* 中序遍历(递归方法)
*/
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. Parcours post-ordre :
/**
* 后序遍历(递归方法)
*/
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);
}Parcours en largeur d'abord :
1. Traversée de niveau :
/**
* 层次遍历(递归方法)
* 由于是按层逐层遍历，因此传递树的层数
*/
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;
}Explication : Dans la méthode level_order2, lors de l'utilisation de la file d'attente, j'utilise la splqueue fournie par la bibliothèque standard PHP SPL If. vous y êtes habitué, si vous utilisez un tableau, vous pouvez utiliser array_push() et array_shift() pour simuler l'implémentation.
Utilisation :
Regardons maintenant le code client :
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();Supplément :
1. Vous pouvez vous référer à l'article précédent pour les trois classes Bst, Avl et Rbt utilisées dans le client : "Explication détaillée de la fonction d'affichage graphique de dessin d'arbres binaires dans PHP"
2. Pourquoi est-ce que je recommande à tout le monde d'utiliser les splstack et splqueue fournis dans la bibliothèque standard SPL ? C'est ce que j'ai vu dans un article : bien que nous puissions utiliser des types de variables traditionnels pour décrire des structures de données, comme utiliser des tableaux pour décrire des piles (Strack) – puis utiliser les méthodes correspondantes pop et push (array_pop(), array_push()), mais il faut toujours être prudent, car après tout, ils ne sont pas spécifiquement conçus pour décrire des structures de données : une mauvaise opération peut détruire la pile. L'objet SplStack de SPL décrit strictement les données sous la forme d'une pile et fournit les méthodes correspondantes. Dans le même temps, un tel code devrait également être capable de comprendre qu'il fonctionne sur une pile plutôt que sur un tableau, permettant à vos pairs de mieux comprendre le code correspondant, et ce sera plus rapide. Adresse d'origine : PHP SPL, la gemme perdue
Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de PHP !
Lecture recommandée :
Explication détaillée du cas de tri par sélection simple PHP
Explication détaillée des étapes pour implémenter l'encodage Huffman /décodage en PHP
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!