PHP基于非递归算法一阶、中阶、末阶遍历二叉树的例子

本文阐述了PHP基于非递归算法的一阶、中阶和后阶遍历二叉树的实现。分享给大家参考，如下：

概述：

二叉树的遍历原理如下：

根据上图所示的二叉树遍历：

1.前言遍历：先遍历根节点，再遍历左子树，最后遍历右子树。

ABDHECFG

2.中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。

HDBEAFCG

3.后序遍历：先遍历左子树，再遍历右子树，最后遍历根节点。

HDEBFGCA

实现方法：

先遍历：利用栈的先进先出特性，先访问根节点，然后按右子树，再按左子树。这样先取出左边的子树，最后取出右边的子树。

函数preorder($ root){ $ stack=array()；array_push($stack，$ root)；while(！空($ stack)){ $ center _ node=array _ pop($ stack)；echo $ center _ node-value；//根节点if($center_node-right！=null) array_push($stack，$ center _ node-right)；//如果($center_node-left)按右子树！=null) array_push($stack，$ center _ node-left)；//按左子树}}顺序：需要从下往上遍历，所以先把左子树按到栈上，然后逐个访问根节点和右子树。

函数inoder($ root){ $ stack=array()；$ center _ node=$ rootwhile(！空($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；}} Postorder:先保存根节点，然后依次保存左子树和右子树。然后输出。

函数tail order($ root){ $ stack=array()；$分站=array()；array_push($$stack，$ root)；while($ empty($ stack)){ $ center _ node=array _ pop($ stack)；array _ push($分站，$ center _ node)；if($ center _ node-右！=null) array_push($stack，$ center _ node-right)；if($center_node-left！=null) array_push($stack，$ center _ node-left)；} while($ empty($分站)){ $ center _ node=array _ pop($分站)；echo $ center _ node-value；}}更多对PHP相关内容感兴趣的读者可以查看本网站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

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