/**
* PHP基于非递归方式算法实现先序/中序/后序遍历二叉树操作
* A
* B C
* D E F G
* H
* 先序遍历:先遍历根节点,然后遍历左节点,最后遍历右节点: ABDHECFG
* 中序遍历:先遍历左子树,然后遍历根节点,最后遍历右子树: HDBEAFCG
* 后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点: HDEBFGCA
* */
/*先序遍历:利用栈的先进后出特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的时候是先取出左子树,最后取出右子树*/
function preOrder($root){
$stack = array();
array_push($stack,$root);
while(!empty($stack)){
$center_node = array_pop($stack);
echo $center_node->value;//根节点
if($center_node->right != null){
array_push($stack,$center_node->right);//压入右子树
}
if($center_node->left != null){
array_push($stack,$center_node->left);//压入左子树
}
}
}
/*中序遍历:需要从下向上遍历,所以先把左子树压入栈,然后逐个访问根节点和右子树*/
function inOrder($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->left;
}
$center_node = array_pop($stack);
echo $center_node->value;
$center_node = $center_node->right;
}
}
/*后序遍历:先把根节点存起来,然后依次存储左子树和右子树,然后输出*/
function tailOrder($root){
$stack = array();
$outStack = array();
array_push($$stack, $root);
while($empty($stack)){
$center_node = array_pop($stack);
array_push($outStack,$center_node);
if($center_node->right != null){
array_push($stack,$center_node->left);
}
}
while($empty($outStack)){
echo $center_node->value;
}
}