<?php

//二叉树的遍历

class Node{

public $value;

public $left;

public $right;

}

//先序遍历 根节点 --->左节点 --->右节点

function preorder ($root) {

$stack = array();

array_push($stack,$root);

while(!empty($stack)) {

$center_node = array_pop($stack); //数组的压入与弹出是以栈道的形式表现的先进后出

echo $center_node->value.' ';

if (!empty($center_node->right)) {

array_push($stack, $center_node->right);

}

if (!empty($center_node->left)) {

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 ($stack != null) {

$center_node = array_pop($stack);

array_push($outstack, $center_node); //先压入根节点

if ($center_node->left != null) {

array_push($stack, $center_node->left);

}

if ($center_node->right != null) {

array_push($stack,$center_node->right);

}

}

while (!empty($outstack)) {

$center_node = array_pop($outstack);

echo $center_node->value;

}

}

$a=new Node();

$b=new Node();

$c=new Node();

$d=new Node();

$e=new Node();

$f=new Node();

$a->value = 'A';

$b->value = 'B';

$c->value = 'C';

$d->value = 'D';

$e->value = 'E';

$f->value = 'F';

$a->left = $b;

$a->right = $c;

$b->left = $d;

$c->left = $e;

$c->right = $f;

tailorder($a);

?>