php 二叉树

         

class Node1 {
         
    public $value;   //节点的数据
    public $leftChild;    //指向左孩子
    public $rightChild;    //指向右孩子
         
    function __construct($value) {
        $this->value = $value;
        $this->leftChild = null;
        $this->rightChild = null;
    }
         
}
//没有跟好的建造树的方法，用土办法
$A = new Node1("A");  
$B = new Node1("B");  
$C = new Node1("C");
$D = new Node1("D");
$E = new Node1("E");
$F = new Node1("F");
$G = new Node1("G");   
$A->leftChild = $B;
$A->rightChild = $C;
$B->leftChild = $D;
$B->rightChild = $E;
$E->rightChild = $G;
$C->leftChild = $F;
print_r($A);
       
class Tree
{  
    
    var $traverse;
   
            
    public function preOrder($tree)
    {
        $this->traverse .= " ".$tree->value;        //根节点的值
        if (! is_null($tree->leftChild)) {            
            $this->preOrder($tree->leftChild);     //左子树 前序遍历
        }
        if (! is_null($tree->rightChild)) {
            $this->preOrder($tree->rightChild);  //右子树 前序遍历
        }
               
    }
           
   
    public function inOrder($tree)
    {
        if (! is_null($tree->leftChild)) {
            $this->inOrder($tree->leftChild);
        }
        $this->traverse .= " ".$tree->value;
        if (! is_null($tree->rightChild)) {
            $this->inOrder($tree->rightChild);
        }
    }
           
   
    public function postOrder($tree)   
    {
        if (! is_null($tree->leftChild)) {
            $this->postOrder($tree->leftChild);
        }
        if (! is_null($tree->rightChild)) {
            $this->postOrder($tree->rightChild);
        }
        $this->traverse .= " ".$tree->value;  
    }
 
                          
    function getPostByinpre($inorder,$preorder)
    {
        if (strlen($preorder)<=0) {
            return ;
        }elseif (strlen($preorder)==1)
        {
            $this->traverse .=" ". $preorder;
            return ;
        }
        //第一个元素师根节点位置
        $k = strpos($inorder,$preorder[0]);  //左子树个数
          
        $temp_preorder = substr($preorder,1,$k);  //左子树   
        $temp_inorder = substr($inorder,0,$k);    //左子树  DBEG BDEG
        $this->getPostByinpre($temp_inorder,$temp_preorder);     
          //中s -> 前e -> 前s
        $preorder_temp = substr($preorder,$k+1,strlen($preorder)-$k-1);  //右子树   FC
        $inorder_temp = substr($inorder,$k+1,strlen($inorder)-$k-1);   //右子树     FC
        $this->getPostByinpre($inorder_temp,$preorder_temp);    
        //后续遍历输出节点
        $this->traverse .=" ".  $preorder[0];
    }
 
 
}
       
$tree = new Tree();
$tree->preOrder($A);
echo "".$tree->traverse;
$tree->traverse = "";
$tree->inOrder($A);
echo "".$tree->traverse;
$tree->traverse = "";
$tree->postOrder($A);
echo "".$tree->traverse;
 
echo "";
unset($tree);
$tree = new Tree();   //   k        1
$tree ->getPostByinpre("DBEGAFC ","ABDEGCF");
echo $tree->traverse;

?>