本文给出了一个PHP如何实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)的例子。分享给大家参考，如下：

前言：

深度优先遍历：每一条可能的分支路径都不能进一步穿透，每个节点只能访问一次。需要注意的是，二叉树的深度优先遍历是特殊的，可以细分为一阶遍历、中阶遍历和末阶遍历。具体说明如下：

前序遍历：根节点-左子树-右子树；左子树-根节点-右子树；后序遍历：左子树-右子树-根节点

广度优先遍历：也叫层次遍历，从上到下依次访问每一层。在每一层中，从左到右(或从右到左)访问节点，然后访问下一层，直到没有节点可以访问。

例如，对于此树：

深度优先遍历：

前序遍历：10 8 7 9 12 11 13中序遍历：7 8 9 10 11 12 13后序遍历：7 9 8 11 13 12 10

广度优先遍历：

层级遍历：10 8 12 7 9 11 13

二叉树深度优先遍历的一般非递归方法是栈，广度优先遍历的一般非递归方法是队列。

深度优先遍历：

1.前言遍历：

/* * *序言遍历(递归方法)*/Private函数pre _ order1 ($ root) {if(！Is_null($root)) {//常量__FUNCTION__在这里用来获取当前的函数名。优点是如果修改函数名，里面的实现不需要修改$ function=_ _ FUNCTION _ _echo $根密钥。' ';$ this-$ function($ root-left)；$ this-$ function($ root-right)；}}/* * *前言遍历(非递归方法)*因为遍历根节点后会回来，所以必须保存。考虑到后进先出法的特点，选择堆栈存储。*/private函数pre _ order 2($ root){//$ stack=new spl stack()；//$ stack-push($ root)；//while(！$ stack-isEmpty()){//$ node=$ stack-pop()；//echo $node-key。' ';//if(！is _ null($ node-right)){//$ stack-push($ node-right)；//} //if(！is _ null($ node-left)){//$ stack-push($ node-left)；//}//} if(is _ null($ root)){ return；} $ stack=new spl stack()；$ node=$ rootwhile(！is_null($node) ||！$stack-isEmpty()) { while(！is _ null($ node){//只要节点不为空，就应该存储在栈中，与其左右节点无关：$ stack-push($ node)；echo $节点键。' ';$ node=$ node-left；} $节点=$ stack-pop()；$ node=$ node-right；}}//Traverse公共函数PreOrder(){ //它所在对象中的树属性保存了一个树引用//$ this-pre _ order 1($ this-树根)；$ this-pre _ order 2($ this-树根)；}描述：1。我已经将所有遍历方法封装在一个类遍历中。2.在pre_order2方法中，在使用栈的过程中，我使用了PHP标准库SPL提供的splstack。如果习惯使用数组，可以使用array_push()和array_pop()来模拟实现。

2.中间顺序遍历：

/*** 中序遍历（递归方法)*/私有函数mid_order1($root){ if(！is _ null($ root)){ $ FUNCTION=_ _ FUNCTION _ _；$ this-$ function($ root-left)；回声$根密钥。' ';$ this-$ function($ root-right)；}}/*** 中序遍历（非递归方法)* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储*/私有函数mid _ order 2($ root){ if(is _ null($ root)){ return；} $ stack=new spl stack()；$ node=$ rootwhile(！is_null($node) ||！$stack-isEmpty()) { while(！is _ null($ node)){ $ stack-push($ node)；$ node=$ node-left；} $节点=$ stack-pop()；回声$节点键。' ';$ node=$ node-right；}}//中序遍历公共函数MidOrder(){//$ this-mid _ order 1($ this-树根);$这-中间订单2($这-树根);}3、后序遍历：

/*** 后序遍历（递归方法)*/私有函数post_order1($root){ if(！is _ null($ root)){ $ FUNCTION=_ _ FUNCTION _ _；$ this-$ function($ root-left)；$ this-$ function($ root-right)；回声$根密钥。' ';}}/*** 后序遍历（非递归方法)* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。* 由于在访问了左子节点后怎么跳到右子节点是难点，这里使用一个标识上次访问来标识上一次访问的结点*/私有函数post _ order 2($ root){ if(is _ null($ root)){ return；} $ node=$ root $ stack=new spl stack()；//保存上一次访问的结点引用$上次访问=空；$ stack-push($ node)；while(！$ stack-isEmpty()){ $ node=$ stack-top()；//获取栈顶元素但不弹出if(($ node-left==NULL $ node-right==NULL)| |($ node-right==NULL $上次访问==$ node-left)| |($上次访问==$ node-right)){ echo $ node-key .' ';$ LastView=$ node $ stack-pop()；} else { if($ node-right){ $ stack-push($ node-right)；} if($ node-left){ $ stack-push($ node-left)；} } }}//后序遍历公共函数post ORder(){//$ this-post _ ORder 1($ this-树根);$这个-post _ order 2($这个-树根);}广度优先遍历：

1、层次遍历：

/* * *层次遍历(递归方法)*因为是逐层遍历，所以传递树的层数*/私有函数level _ order1 ($ root，$ level){ if($ root==null | | $ level 1){ return；} if($level==1){ echo $root-key。' ';返回；} if(！is _ null($ root-left)){ $ this-level _ order 1($ root-left，$ level-1)；} if(！is _ null($ root-right)){ $ this-level _ order 1($ root-right，$ level-1)；}}/* * *分层遍历(非递归方法)*每层从左到右输出的元素需要用先进先出的特性存储，所以选择队列存储。*/私有函数level _ order 2($ root){ if(is _ null($ root)){ return；} $ node=$ root//用队列实现//$ queue=array()；//array_push($queue，$ node)；////while(！is _ null($ node=array _ shift($ queue)){//echo $ node-key。' ';//if(！is _ null($ node-left)){//array _ push($ queue，$ node-left)；//}//if(！is _ null($ node-right)){//array _ push($ queue，$ node-right)；//}/} $ queue=new sp queue()；$ queue-enqueue($ node)；while(！$ queue-isEmpty()){ $ node=$ queue-queue()；echo $节点键。' ';if(！is _ null($ node-left)){ $ queue-enqueue($ node-left)；} if(！is _ null($ node-right)){ $ queue-enqueue($ node-right)；} } }//遍历公共函数级顺序(){//$ level=$ this-get depth($ this-tree-root)；//for($ I=1；$ i=$ level$ I){//$ this-level _ order 1($ this-树根，$ I)；//} $ this-level _ order 2($ this-树根)；}//获取树的层数私有函数get depth($ root){ if(is _ null($ root)){ return 0；} $ left=get depth($ root-left)；$ right=get depth($ root-right)；$depth=($left $right？$ left : $ right)1；返回$ depth}说明：在level_order2方法中，在使用queue的过程中，我使用了PHP标准库spl提供的SPLqueue。如果习惯使用array，可以使用array_push()和array_shift()来模拟。

使用：

现在让我们看看客户端代码：

class client { public static function main(){ try {//实现文件的自动加载。函数autoload($ class){包含strtolow($ class)。PHP '；} spl _ autoload _ register(' autoload ')；$arr=array(10，8，12，7，9，11，13)；$ tree=new Bst()；//$ tree=new Avl()；//$ tree=new Rbt()；$ tree-init($ arr)；$ traverse=new traverse($ tree)；$ traverse-PreOrder()；//$ traverse-MidOrder()；//$ traverse-PostOrder()；//$ traverse-level order()；} catch(Exception $ e){ echo $ e-getMessage()；} } } client :3360 main()；补充：

1.客户端使用的三个类Bst、Avl和Rbt可以参考前一个：《PHP实现绘制二叉树图形显示功能详解》

2.为什么我推荐你使用spl标准库中提供的SPLstack和splqueue？这是我在一篇文章中看到的：虽然我们可以使用传统的变量类型来描述数据结构，例如，使用数组来描述堆栈——然后使用相应的方法pop和push(array_pop())、array_push())，但您应该始终小心，因为毕竟它们不是专门用来描述数据结构的——一个错误的操作可能会破坏堆栈。spl的SPLstack对象严格以栈的形式描述数据，并提供相应的方法。同时这样的代码应该能够理解它是在操作栈而不是数组，这样你的同伴才能更好的理解对应的代码，而且速度更快。原地址：phpsl，失落的宝石

3.本文相关参考文章：《C语言二叉树常见操作详解【前序，中序，后序，层次遍历及非递归查找，统计个数，比较，求深度】》，《Java实现二叉树的深度优先遍历和广度优先遍历算法示例》

更多对PHP相关内容感兴趣的读者可以查看本网站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。