首页 >后端开发 >php教程 >PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作

PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作

不言原创: 2018-04-26 16:18:011639浏览

这篇文章主要介绍了关于PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下

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

PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作

相关文章