最新公告
  • 欢迎您光临002y资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • php实现的二叉树遍历算法示例

    正文概述    2022-08-06   14

    本文实例讲述了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程序设计有所帮助。


    002y资源网 » php实现的二叉树遍历算法示例

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    微信支付
    余额支付
    ×
    微信扫码支付 0 元