PHP implémente des opérations d'arbre binaire de traversée de pré-commande/dans-la-commande/post-commande basées sur un algorithme non récursif

Cet article présente principalement l'implémentation par PHP d'opérations d'arbre binaire de traversée en pré-commande/en commande/post-commande basées sur des algorithmes non récursifs. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. à lui

/**
 * PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作
 *          A
 *       B      C
 *    D    E  F     G
 *  H  
  * 先序遍历:先遍历根节点,然后遍历左节点,最后遍历右节点: ABDHECFG 
 * 中序遍历:先遍历左子树,然后遍历根节点,最后遍历右子树:  HDBEAFCG
 * 后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点: 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->left);
 }
 }
 while($empty($outStack)){
 echo $center_node->value;
 }
 }

Recommandations associées :

Le mode itérateur de PHP implémenté sur la base de SPL

Explication détaillée de la méthode PHP de génération de QR codes basés sur la classe phpqrcode

PHP implémente la fonction de livre d'or basée sur l'orientation objet

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!