PHP implements pre-order/in-order/post-order traversal binary tree operations based on non-recursive algorithm

This article mainly introduces the implementation of pre-order/in-order/post-order traversal binary tree operations in PHP based on non-recursive algorithms. It has a certain reference value. Now I share it with you. Friends in need can refer to it

/**
 * 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;
 }
 }

Related recommendations:

Iterator mode implemented by PHP based on SPL

Detailed explanation of the method of generating QR code in PHP based on the phpqrcode class

PHP implements the guestbook function based on object-oriented

The above is the detailed content of PHP implements pre-order/in-order/post-order traversal binary tree operations based on non-recursive algorithm. For more information, please follow other related articles on the PHP Chinese website!