<?php
/**
* PHP实现二叉树遍历(非递归方式，栈模拟实现)
* 二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式：
* ① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
* ——访问结点的操作发生在遍历其左右子树之前。
* ② LNR：中序遍历(InorderTraversal)
* ——访问结点的操作发生在遍历其左右子树之中(间)。
* ③ LRN：后序遍历(PostorderTraversal)
* ——访问结点的操作发生在遍历其左右子树之后。
*/
class node
{
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = $value;
}
}
//前序遍历，访问根节点->遍历子左树->遍历子右树
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) {
// 遍历节点
while ($center_node) {
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 postorder($root) {
$pushstack = array();
$visitstack = array();
array_push($pushstack, $root);
while (!empty($pushstack)) {
$center_node = array_pop($pushstack);
array_push($visitstack, $center_node);
if ($center_node->left != null) {
array_push($pushstack, $center_node->left);
}
if ($center_node->right != null) {
array_push($pushstack, $center_node->right);
}
}
while (!empty($visitstack)) {
$center_node = array_pop($visitstack);
echo $center_node->value . ' ';
}
}
$a = new node('A');
$b = new node('B');
$c = new node('C');
$d = new node('D');
$e = new node('E');
$f = new node('F');
$a->left = $b;
$a->right = $c;
$b->left = $d;
$b->right = $d;
$c->left = $e;
$c->right = $f;
preorder($a);
echo '<br />';
inorder($a);
echo '<br />';
postorder($a);