PHP implémente un parcours en profondeur (pré-commande, intermédiaire, post-commande) et en largeur (niveau) des arbres binaires

Cet article présente principalement PHP pour implémenter le parcours en profondeur (pré-commande, dans l'ordre, post-commande) et le parcours en largeur (niveau) des arbres binaires. Il combine des exemples avec une analyse détaillée de la profondeur de PHP. première traversée et traversée en largeur d'arbres binaires. Pour connaître les compétences opérationnelles et les précautions associées, les amis dans le besoin peuvent se référer à

Cet article décrit la mise en œuvre de la traversée en profondeur (précommande, commande intermédiaire, publication). -ordre) et parcours en largeur (niveau) d'un arbre binaire en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Avant-propos :

Traversée en profondeur d'abord : pour toutes les possibilités Le chemin de branchement va aussi loin qu'il ne peut aller plus loin, 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 en 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. J'ai encapsulé toutes les méthodes de parcours 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 array_push() et array_pop() pour simuler l'implémentation.

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.

/**
* 后序遍历(递归方法)
*/
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);
}

Traversée en largeur :

1. traversal:

/**
* 层次遍历(递归方法)
* 由于是按层逐层遍历，因此传递树的层数
*/
private function level_order1($root,$level){
    if($root == NULL || $level < 1){
      return;
    }
    if($level == 1){
      echo $root->key.&#39; &#39;;
      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.&#39; &#39;;
//      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.&#39; &#39;;
      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;
}

Remarque : Dans la méthode level_order2, lors de l'utilisation de la file d'attente, j'utilise la splqueue fournie par le standard PHP bibliothèque SPL , si vous avez l'habitude d'utiliser des tableaux, vous pouvez utiliser

et array_push() pour simuler l'implémentation. array_shift()

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 Les trois classes Bst, Avl et Rbt utilisées dans le client Tout le monde Vous pouvez vous référer. l'article précédent : "Explication détaillée de la fonction d'affichage graphique pour dessiner des arbres binaires en PHP"

2. Pourquoi je vous recommande d'utiliser les

et splstack 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 (splqueue, array_pop()), 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 array_push()

3. Articles de référence liés à cet article : "Explication détaillée des opérations courantes sur les arbres binaires en langage C [précommande, inordre, post-ordre, parcours hiérarchique et non- recherche récursive, comptez le nombre, comparez et trouvez la profondeur]", "Implémentation Java d'algorithmes de traversée en profondeur et en largeur pour les arbres binaires"

Recommandations associées :

Algorithme de tri PHP bouillonnant Sort (Bubble Sort)

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!