<?php
//構(gòu)建節(jié)點類
class Node
{
    private $keys;//節(jié)點值
    private $left,$right;//左子節(jié)點、右子節(jié)點
    //當(dāng)前節(jié)點的值，以及左子節(jié)點、右子節(jié)點
    public function __construct($key,$left,$right){
        $this->keys=$key;
        $this->left=$left;
        $this->right=$right;
    }
    function getKey(){
        return $this->keys;
    }
    function setKey($i){
        $this->keys=$i;
    }
    function getLeft(){
        return $this->left;
    }
    function setLeft($l){
        $this->left=$l;
    }
    function getRight(){
        return $this->right;
    }
    function setRight($r){
        $this->right=$r;
    }
}
class BinaryTree
{
    /** 構(gòu)造樹 */  
    static function init(){
        $a= new Node(1,null,null);
        $b= new Node(2,null,$a);
        $c= new Node(3,null,null);
        $d= new Node(4,$b,$c);
        $e= new Node(5,null,null);
        $f= new Node(6,$e,null);
        $g= new Node(7,null,$f);
        $h= new Node(8,$d,$g);
        return $h;
    }
    function visit($n){
        echo $n->getKey()." ";
    }
    //前序遍歷 根節(jié)點->左子節(jié)點->右子節(jié)點
    function preorder($n){
        if($n != null){
            $this->visit($n);
            $this->preorder($n->getLeft());
            $this->preorder($n->getRight());
        }
    }
    //中序遍歷 左子節(jié)點->根節(jié)點->右子節(jié)點
    function inorder($n){
        if($n != null){
            $this->inorder($n->getLeft());
            $this->visit($n);
            $this->inorder($n->getRight());
        }
    }
    //后序遍歷 左子節(jié)點->右子節(jié)點->根節(jié)點
    function postorder($n){
        if($n != null){
            $this->postorder($n->getLeft());
            $this->postorder($n->getRight());
            $this->visit($n);
        }
    }
}
$c=new BinaryTree;
$root=BinaryTree::init();
//$c->visit($root);
echo "前序遍歷\n";
$c->preorder($root);
echo "\n中序遍歷\n";
$c->inorder($root);
echo "\n后序遍歷\n";
$c->postorder($root);