php语言

php如何实现的二叉树遍历(示例)

时间:2024-10-17 21:09:39 php语言 我要投稿
  • 相关推荐

php如何实现的二叉树遍历(示例)

  本文主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考一下!想了解更多相关信息请持续关注我们应届毕业生考试网!

  创建的二叉树如下图所示

  php代码如下所示:

  <?php

  class Node {

  public $value;

  public $child_left;

  public $child_right;

  }

  final class Ergodic {

  //前序遍历:先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树

  public static function preOrder($root){

  $stack = array();

  array_push($stack, $root);

  while(!empty($stack)){

  $center_node = array_pop($stack);

  echo $center_node->value . ' ';

  //先把右子树节点入栈,以确保左子树节点先出栈

  if($center_node->child_right != null) array_push($stack, $center_node->child_right);

  if($center_node->child_left != null) array_push($stack, $center_node->child_left);

  }

  }

  //中序遍历:先遍历左子树、然后访问根节点,最后遍历右子树;并且在遍历左右子树的时候。仍然是先遍历左子树,然后访问根节点,最后遍历右子树

  public static function midOrder($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->child_left;

  }

  $center_node = array_pop($stack);

  echo $center_node->value . ' ';

  $center_node = $center_node->child_right;

  }

  }

  //后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点;同样,在遍历左右子树的时候同样要先遍历左子树,然后遍历右子树,最后访问根节点

  public static function endOrder($root){

  $push_stack = array();

  $visit_stack = array();

  array_push($push_stack, $root);

  while (!empty($push_stack)) {

  $center_node = array_pop($push_stack);

  array_push($visit_stack, $center_node);

  //左子树节点先入$pushstack的栈,确保在$visitstack中先出栈

  if ($center_node->child_left != null) array_push($push_stack, $center_node->child_left);

  if ($center_node->child_right != null) array_push($push_stack, $center_node->child_right);

  }

  while (!empty($visit_stack)) {

  $center_node = array_pop($visit_stack);

  echo $center_node->value . ' ';

  }

  }

  }

  //创建二叉树

  $a = new Node();

  $b = new Node();

  $c = new Node();

  $d = new Node();

  $e = new Node();

  $f = new Node();

  $g = new Node();

  $h = new Node();

  $i = new Node();

  $a->value = 'A';

  $b->value = 'B';

  $c->value = 'C';

  $d->value = 'D';

  $e->value = 'E';

  $f->value = 'F';

  $g->value = 'G';

  $h->value = 'H';

  $i->value = 'I';

  $a->child_left = $b;

  $a->child_right = $c;

  $b->child_left = $d;

  $b->child_right = $g;

  $c->child_left = $e;

  $c->child_right = $f;

  $d->child_left = $h;

  $d->child_right = $i;

  //前序遍历

  Ergodic::preOrder($a); //结果是:A B D H I G C E F

  echo '<br/>';

  //中序遍历

  Ergodic::midOrder($a); //结果是: H D I B G A E C F

  echo '<br/>';

  //后序遍历

  Ergodic::endOrder($a); //结果是: H I D G B E F C A


《php如何实现的二叉树遍历(示例).doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档

【php如何实现的二叉树遍历(示例)】相关文章:

PHP使用递归算法无限遍历数组示例05-20

PHP中多态如何实现09-04

php如何实现验证码06-13

PHP中如何实现crontab代码05-30

如何实现PHP图片裁剪与缩放07-13

PHP遍历目录文件常用方法09-23

php递归遍历多维数组的方法10-06

PHP如何使用curl实现数据抓取09-27

用PHP遍历目录下的全部文件06-13

如何实现PHP获取表单数据与HTML嵌入PHP脚本09-23

php如何实现的二叉树遍历(示例)

  本文主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考一下!想了解更多相关信息请持续关注我们应届毕业生考试网!

  创建的二叉树如下图所示

  php代码如下所示:

  <?php

  class Node {

  public $value;

  public $child_left;

  public $child_right;

  }

  final class Ergodic {

  //前序遍历:先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树

  public static function preOrder($root){

  $stack = array();

  array_push($stack, $root);

  while(!empty($stack)){

  $center_node = array_pop($stack);

  echo $center_node->value . ' ';

  //先把右子树节点入栈,以确保左子树节点先出栈

  if($center_node->child_right != null) array_push($stack, $center_node->child_right);

  if($center_node->child_left != null) array_push($stack, $center_node->child_left);

  }

  }

  //中序遍历:先遍历左子树、然后访问根节点,最后遍历右子树;并且在遍历左右子树的时候。仍然是先遍历左子树,然后访问根节点,最后遍历右子树

  public static function midOrder($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->child_left;

  }

  $center_node = array_pop($stack);

  echo $center_node->value . ' ';

  $center_node = $center_node->child_right;

  }

  }

  //后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点;同样,在遍历左右子树的时候同样要先遍历左子树,然后遍历右子树,最后访问根节点

  public static function endOrder($root){

  $push_stack = array();

  $visit_stack = array();

  array_push($push_stack, $root);

  while (!empty($push_stack)) {

  $center_node = array_pop($push_stack);

  array_push($visit_stack, $center_node);

  //左子树节点先入$pushstack的栈,确保在$visitstack中先出栈

  if ($center_node->child_left != null) array_push($push_stack, $center_node->child_left);

  if ($center_node->child_right != null) array_push($push_stack, $center_node->child_right);

  }

  while (!empty($visit_stack)) {

  $center_node = array_pop($visit_stack);

  echo $center_node->value . ' ';

  }

  }

  }

  //创建二叉树

  $a = new Node();

  $b = new Node();

  $c = new Node();

  $d = new Node();

  $e = new Node();

  $f = new Node();

  $g = new Node();

  $h = new Node();

  $i = new Node();

  $a->value = 'A';

  $b->value = 'B';

  $c->value = 'C';

  $d->value = 'D';

  $e->value = 'E';

  $f->value = 'F';

  $g->value = 'G';

  $h->value = 'H';

  $i->value = 'I';

  $a->child_left = $b;

  $a->child_right = $c;

  $b->child_left = $d;

  $b->child_right = $g;

  $c->child_left = $e;

  $c->child_right = $f;

  $d->child_left = $h;

  $d->child_right = $i;

  //前序遍历

  Ergodic::preOrder($a); //结果是:A B D H I G C E F

  echo '<br/>';

  //中序遍历

  Ergodic::midOrder($a); //结果是: H D I B G A E C F

  echo '<br/>';

  //后序遍历

  Ergodic::endOrder($a); //结果是: H I D G B E F C A