PHP二叉树的初体验
$a=new Node();
$b=new Node();
$c=new Node();
$d=new Node();
$e=new Node();
$f=new Node();
$g=new Node();
$h=new Node();
$i=new Node();
$j=new Node();
$k=new Node();
$a->value='A';
$b->value='B';
$c->value='C';
$d->value='D';
$e->value='E';
$f->value='F';
$g->value='G';
$h->value='H';
$i->value='I';
$j->value='J';
$k->value='K';
$a->left=$b;
$a->right=$g;
$b->left=$c;
$b->right=$f;
$c->left=$d;
$c->right=$e;
$g->left=$h;
$g->right=$i;
$i->left=$j;
$i->right=$k;
echo '非递归算法<br><hr/>';
echo 'preorder_<br><hr/>';
preorder_($a);//A B C D E F G H I J K
echo '<br>inorder_<br><hr/>';
inorder_($a);//D C E B F A H G J I K
echo '<br>tailorder_<br><hr/>';
tailorder_($a);//D E C F B H J K I G A
echo '<br><br>递归算法<br><hr/>';
echo 'preorder<br><hr/>';
preorder($a);//A B C D E F G H I J K
echo '<br>inorder<br><hr/>';
inorder($a);//D C E B F A H G J I K
echo '<br>tailorder<br><hr/>';
tailorder($a);//D E C F B H J K I G A
class Node {
public $value;
public $left;
public $right;
}
function preorder(Node $node){
if($node->value){
echo $node->value.' ';
}
if($node->left){
preorder($node->left);
}
if($node->right){
preorder($node->right);
}
}
function inorder(Node $node){
if($node->left){
inorder($node->left);
}
if($node->value){
echo $node->value.' ';
}
if($node->right){
inorder($node->right);
}
}
function tailorder(Node $node){
if($node->left){
tailorder($node->left);
}
if($node->right){
tailorder($node->right);
}
if($node->value){
echo $node->value.' ';
}
}
function preorder_(Node $node){
$stack = array();
array_push($stack, $node);
while(!empty($stack)){
$tmp = array_pop($stack);
echo $tmp->value.' ';
if($tmp->right){
array_push($stack, $tmp->right);
}
if($tmp->left){
array_push($stack, $tmp->left);
}
}
}
function inorder_(Node $node){
$stack = array();
$tmp = $node;
while($tmp || !empty($stack)){
if($tmp){
array_push($stack, $tmp);
$tmp = $tmp->left;
}else{
$tmp = array_pop($stack);
echo $tmp->value.' ';
$tmp= $tmp->right;
}
}
}
function tailorder_(Node $node){
$stack = array();
$outstack = array();
$tmp = $node;
array_push($stack, $tmp);
// while 外 先压$outstack后出$outstack
while(!empty($stack)){
$tmp = array_pop($stack);
array_push($outstack, $tmp);
// while 内 先压$stack先出$outstack
if($tmp->left){
array_push($stack, $tmp->left);
}
if($tmp->right){
array_push($stack, $tmp->right);
}
}
while(!empty($outstack)){
$tmp = array_pop($outstack);
echo $tmp->value.' ';
}
}
——————————
运行效果:
