<?php
//构建节点类
class Node
{
    private $keys;//节点值
    private $left,$right;//左子节点、右子节点
    //当前节点的值，以及左子节点、右子节点
    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
{
    /** 构造树 */  
    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()." ";
    }
    //前序遍历 根节点->左子节点->右子节点
    function preorder($n){
        if($n != null){
            $this->visit($n);
            $this->preorder($n->getLeft());
            $this->preorder($n->getRight());
        }
    }
    //中序遍历 左子节点->根节点->右子节点
    function inorder($n){
        if($n != null){
            $this->inorder($n->getLeft());
            $this->visit($n);
            $this->inorder($n->getRight());
        }
    }
    //后序遍历 左子节点->右子节点->根节点
    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);