微信号:phpdaily

介绍:PHP在线专注于PHP编程语言学习,PHP开发经验分享,工作问题解决以及PHP在线技能测评等多功能为一体的服务系统,希望给工作学习中的PHPER带来些帮助。

二叉树遍历算法

2018-07-10 22:46 Lane

微信公众号:PHP在线

二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次。

前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为ABCDEGF。

中序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从根节点开始,中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树,遍历顺序为CBEGDFA。

后序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从左到右先叶子后节点的访问遍历访问左右子树,最后是访问根节点。访问顺序为CGEFDBA。

层序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从树的第一层,也就是根节点开始访问,从上而下逐层遍历,在同一层中,按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。

现在,我们用PHP代码,来遍历二叉树结构。二叉树是放一个大数组,每一个节点都有三个字段,data表示这个节点的值,lChild表示这个节点的左边子节点,rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。

二叉树结构代码如下:

<?php

//二叉树

$arr = array(

   'data' => 'A',

   'lChild' => array(

       'data' => 'B',

       'lChild' => array(

           'data' => 'C',

           'lChild' => array(),

           'rChild' => array(),

       ),

       'rChild' => array(

           'data' => 'D',

           'lChild' => array(

               'data' => 'E',

               'lChild' => array(),

               'rChild' => array(

                   'data' => 'G',

                   'lChild' => array(),

                   'rChild' => array(),

               ),

           ),

           'rChild' => array(

               'data' => 'F',

               'lChild' => array(),

               'rChild' => array(),

           ),

       ),

   ),

   'rChild' => array(),

);

遍历算法一:前序遍历二叉树

<?php

//前序遍历二叉树算法

echo '前序遍历二叉树算法:';

PreOrderTraverse($arr);

echo '<Br>';

function PreOrderTraverse($node){

   if(empty($node)){

       return;

   }

   //输出值

   print_r($node['data']);

   //左节点

   PreOrderTraverse($node['lChild']);

   //右节点

   PreOrderTraverse($node['rChild']);

}

遍历算法二:中序遍历二叉树

<?php

//中序遍历二叉树算法

echo '中序遍历二叉树算法:';

inOrderTraverse($arr);

echo '<Br>';

function inOrderTraverse($node){

   if(empty($node)){

       return;

   }

   //左节点

   inOrderTraverse($node['lChild']);

   //输出值

   print_r($node['data']);

   //右节点

   inOrderTraverse($node['rChild']);

}

遍历算法三:后序遍历二叉树

<?php

//后序遍历二叉树算法

echo '后序遍历二叉树算法:';

postOrderTraverse($arr);

echo '<Br>';

function postOrderTraverse($node){

   if(empty($node)){

       return;

   }

   //左节点

   postOrderTraverse($node['lChild']);

   //右节点

   postOrderTraverse($node['rChild']);

   //输出值

   print_r($node['data']);

}


 
PHP在线 更多文章 PHP面试题 Redis数据结构详解,五种数据结构分分钟掌握 PHP开发一个属于自己MVC框架 这些GIT经验够你用一年了 如何发挥出PHP7的高性能
猜您喜欢 猜猜 CODING 愚人节会有什么惊喜? Google《重新定义公司》笔记 Python基础教程5:运算符 设备适应