<?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 = http://www.mamicode.com/‘A‘;
$b->value = http://www.mamicode.com/‘B‘;
$c->value = http://www.mamicode.com/‘C‘;
$d->value = http://www.mamicode.com/‘D‘;
$e->value = http://www.mamicode.com/‘E‘;
$f->value = http://www.mamicode.com/‘F‘;
$a->left = $b;
$a->right = $c;
$b->left = $d;
$c->left = $e;
$c->right = $f;
tailorder($a);
?>

二叉树