二叉樹圖

<?php

class Node {  
    public $value;  
    public $child_left;  
    public $child_right;  
}  
final class  Ergodic {  
    //前序遍歷:先訪問(wèn)根節(jié)點(diǎn)沫屡，再遍歷左子樹疙剑，最后遍歷右子樹搂鲫；并且在遍歷左右子樹時(shí)平绩，仍需先遍歷根節(jié)點(diǎn)，然后訪問(wèn)左子樹尔破，最后遍歷右子樹  
    public static function preOrder($root){  
        $stack = array();  
        array_push($stack, $root);  
        while(!empty($stack)){  
            $center_node = array_pop($stack);  
            echo $center_node->value . ' ';  
  
            //先把右子樹節(jié)點(diǎn)入棧航夺，以確保左子樹節(jié)點(diǎn)先出棧  
            if($center_node->child_right != null) array_push($stack, $center_node->child_right);  
            if($center_node->child_left != null) array_push($stack, $center_node->child_left);  
        }  
    }  
    //中序遍歷:先遍歷左子樹划提、然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹；并且在遍歷左右子樹的時(shí)候洽腺。仍然是先遍歷左子樹脚粟，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹  
    public static function midOrder($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->child_left;  
            }  
  
            $center_node = array_pop($stack);  
            echo $center_node->value . ' ';  
  
            $center_node = $center_node->child_right;  
        }  
    }  
    //后序遍歷:先遍歷左子樹蘸朋，然后遍歷右子樹核无，最后訪問(wèn)根節(jié)點(diǎn)；同樣藕坯，在遍歷左右子樹的時(shí)候同樣要先遍歷左子樹团南，然后遍歷右子樹，最后訪問(wèn)根節(jié)點(diǎn)  
    public static function endOrder($root){  
        $push_stack = array();  
        $visit_stack = array();  
        array_push($push_stack, $root);  
  
        while (!empty($push_stack)) {  
            $center_node = array_pop($push_stack);  
            array_push($visit_stack, $center_node);  
            //左子樹節(jié)點(diǎn)先入$pushstack的棧炼彪，確保在$visitstack中先出棧  
            if ($center_node->child_left != null) array_push($push_stack, $center_node->child_left);  
            if ($center_node->child_right != null) array_push($push_stack, $center_node->child_right);  
        }  
  
        while (!empty($visit_stack)) {  
            $center_node = array_pop($visit_stack);  
            echo $center_node->value . ' ';  
        }  
    }  
}  
  
  
//創(chuàng)建二叉樹  
$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();  
  
$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';  
  
$a->child_left = $b;  
$a->child_right = $c;  
$b->child_left = $d;  
$b->child_right = $g;  
$c->child_left = $e;  
$c->child_right = $f;  
$d->child_left = $h;  
$d->child_right = $i;  
  
  
//前序遍歷  
Ergodic::preOrder($a);  //結(jié)果是：A B D H I G C E F  
echo '<br/>';  
//中序遍歷  
Ergodic::midOrder($a);  //結(jié)果是： H D I B G A E C F  
echo '<br/>';  
//后序遍歷  
Ergodic::endOrder($a); //結(jié)果是:  H I D G B E F C A