Heim  >  Artikel  >  Backend-Entwicklung  >  PHP implementiert Vorbestellungs-/In-Bestellungs-/Nachbestellungs-Traversal-Binärbaumoperationen basierend auf einem nicht-rekursiven Algorithmus

PHP implementiert Vorbestellungs-/In-Bestellungs-/Nachbestellungs-Traversal-Binärbaumoperationen basierend auf einem nicht-rekursiven Algorithmus

不言
不言Original
2018-04-26 16:18:011611Durchsuche

Dieser Artikel stellt hauptsächlich die Implementierung von Binärbaumoperationen vor der Bestellung/in der Bestellung/nach der Bestellung vor, die auf nicht rekursiven Algorithmen basieren. Jetzt teile ich ihn mit Ihnen kann darauf verweisen

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

Verwandte Empfehlungen:

PHPs Iteratormodus basierend auf SPL implementiert

Detaillierte Erklärung, wie PHP QR-Codes generiert basierend auf der phpqrcode-Klasse

PHP implementiert die Gästebuchfunktion basierend auf objektorientierten

Das obige ist der detaillierte Inhalt vonPHP implementiert Vorbestellungs-/In-Bestellungs-/Nachbestellungs-Traversal-Binärbaumoperationen basierend auf einem nicht-rekursiven Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn