<?php
/*******************************************
 *
 * 作者:    外来物种

 * 创建:    2007-9-25

 * 企鹅:    151666859

 * 修改:    2007-9-29
 *
 *******************************************/

class Tree{
    /**
    * 树型数据,经过排序的记录集
    */
    var $mRsTree = array();

    var $mMaps   = array();

    /**
     * id字段名 父id的字段名 根id的值
     */
    var $mFdId   = null;
    var $mFdFId  = null;
    var $mRId    = null;

    /**
     *
     * 构造函数
     *
     */
    function Tree($rsTree,$fdId = "id",$fdFId = "pid",$rootId = 0)
    {
        $this->mFdId    = $fdId;
        $this->mFdFId   = $fdFId;
        $this->mRId     = $rootId;

        $this->mRsTree  = $this->AddLevelInfo($rsTree);
        $this->SetMaps();
    }


    
    /**
     *
     * 取得到某一节点的路径
     *
     */
    public function GetTrackNodes($id,$level = 1,$fields = '*')
    {
        $tracks = array();
        
        do{
            $id_index = $this->mMaps[$id];
            $tracks[] = $this->FetchByFields( $id_index ,$fields);
            $id       = $this->mRsTree[ $id_index ][ $this->mFdFId ];
        }while( isset($this->mMaps[$id])
                && $id != $this->mRId 
                && $this->FetchByFields( $this->mMaps[$id] ,'level') >= $level);

        return array_reverse($tracks);
    }

    /**
     *
     * 取得某层的所有节点
     *
     */
    public function GetLevelNodes($level,$fields = '*')
    {
        $ret_nodes = array();

        foreach($this->mRsTree AS $i=>$r){
            if( $r['level'] == $level ){
                $ret_nodes[] = $this->FetchByFields( $i ,$fields);
            }
        }

        return $ret_nodes;
    }

    /**
     *
     * 取得某个节点的叶子节点
     *
     */
    public function GetLeafNodes($id,$fields = '*')
    {
        $ret_nodes  = array();

        //获得主键为$id 记录在数组中的索引号
        $id_index = $this->mMaps[$id];
        $id_level = $this->mRsTree[ $id_index ]['level'];

        //当前节点是叶子节点
        if( !$this->HasChild($id) ){
            $ret_nodes[] = $this->FetchByFields( $id_index ,$fields);
            return $ret_nodes;
        }
        //当前节点不是叶子节点
        $id_index++;

        while(isset($this->mRsTree[$id_index]) && $this->mRsTree[$id_index]['level'] > $id_level){

            if( !isset($this->mRsTree[$id_index+1]) || $this->mRsTree[$id_index]['level'] >= $this->mRsTree[$id_index+1]['level'] ){
                $ret_nodes[] = $this->FetchByFields( $id_index ,$fields);
            }
            
            $id_index++;
        }

        return $ret_nodes;
    }

    /**
     *
     * 取得某个节点的子孩子
     *
     */
    public function GetChildNodes($id,$fields = '*')
    {
        $ret_nodes  = array();

        //获得 id=$id 记录在数组中的索引号和层次
        $id_level = $this->mRsTree[ $this->mMaps[$id] ]['level'];
        $id_index = $this->mMaps[$id];
        
        $rs_cnt     = count($this->mRsTree);

        for($i=$id_index+1; $i < $rs_cnt; $i++){
            if( $this->mRsTree[$i]['level'] <= $id_level )
                break;

            $ret_nodes[] = $this->FetchByFields( $i ,$fields);
        }

        return $ret_nodes;
    }

    /**
     *
     * 取得某个节点的子孩子
     *
     */
    public function GetParentNodes($id,$fields = '*')
    {
        //获得 id=$id 记录在数组中的索引号和层次
        $id_fid     = $this->mRsTree[ $this->mMaps[$id] ][ $this->mFdFId ];
        $id_index   = $this->mMaps[$id];

        $rs_cnt     = count($this->mRsTree);

        for($i=$id_index; $i >= 0; $i--){
            if( $this->mRsTree[$i][$this->mFdId] == $id_fid )
                return  $this->FetchByFields( $i ,$fields);
        }
    }

    /**
    *
    * implode 的增强函数
    *
    */
    public function Implodei($sep,$arr)
    {
        $ret_a = array();

        foreach($arr AS $key=>$val){
            if( is_array($val) ){
                $ret_a[] = $this->ImplodeI($sep,$val);
            }
            else{
                return implode($sep,$arr);
            }
        }

        return implode($sep,$ret_a);
    }

    /**
    *
    * 按字段取得某条树型记录
    *
    */
    private function FetchByFields($index,$fields)
    {
        $rets = array();

        if($fields == '*'){
            $rets = $this->mRsTree[ $index ];
        }
        else if( is_array($fields) ){
            $tmp_r = array();
            foreach($fields AS $k => $v){
                $tmp_r[$v] = $this->mRsTree[ $index ][$v];
            }
            $rets = $tmp_r;
        }
        else{
            $rets[$fields] = $this->mRsTree[ $index ][$fields];
        }

        return $rets;
    }

    private function HasChild($id)
    {
        $id_index = $this->mMaps[$id];
        $id_level = $this->mRsTree[$id_index]['level'];
        
        if( isset($this->mRsTree[$id_index+1]) )
            if($this->mRsTree[$id_index+1]['level'] > $id_level)
                return true;

        return false;
    }

    /**
     *
     * 增加层次信息
     *
     */
    private function AddLevelInfo($rsTree)
    {
        //树型排序
        $rsTree = $this->SortToTreeRs($rsTree);

        //增加 level 信息
        $levels = array();

        foreach($rsTree AS $i => $r){
            if($r[ $this->mFdFId ] == $this->mRId){
                $rsTree[$i]['level'] = 1;
                $levels[ $r[ $this->mFdId ] ] = $rsTree[$i]['level'];
            }
            else{
                $rsTree[$i]['level'] = $levels[ $r[ $this->mFdFId ] ] + 1;
                $levels[ $r[ $this->mFdId ] ] = $rsTree[$i]['level'];
            }
        }
       
        return $rsTree;
    }

    private function SetMaps()
    {
        $rs_cnt     = count($this->mRsTree);

        for($i=0; $i < $rs_cnt; $i++){
            $this->mMaps[ $this->mRsTree[$i][$this->mFdId] ] = $i;
        }
    }
    
    /**
     *
     * 将树型记录集按树型排序
     *
     *   array("id"=>4,"fid"=>2)       array("id"=>4,"fid"=>0)
     *   array("id"=>4,"fid"=>0)  =>   array("id"=>2,"fid"=>4)
     *   array("id"=>2,"fid"=>4)       array("id"=>5,"fid"=>2)
     *
     */
    private function SortToTreeRs($rsTree)
    {
        $rs_cnt = count($rsTree);

        for($i=0; $i < $rs_cnt; $i++){
            $float_ind  = $i;
            $cur_fid    = $rsTree[$i][$this->mFdFId];
            
            //上浮索引
            while($float_ind > 0 && $cur_fid != $rsTree[$float_ind-1][$this->mFdId]){             
                $float_ind--;
            }

            //浮动终止，替换内容
            if($float_ind != $i){
                array_splice( $rsTree,$float_ind,0,array_splice($rsTree,$i,1) );
            }
        }

        return $rsTree;
    }
}

$rsTree = array(
    array("id"=>3,"fid"=>6,"title"=>"节点3"),
    array("id"=>7,"fid"=>0,"title"=>"节点7"),
    array("id"=>22,"fid"=>7,"title"=>"节点22"),
    array("id"=>1,"fid"=>7,"title"=>"节点1"),
    array("id"=>6,"fid"=>22,"title"=>"节点6"),
    array("id"=>8,"fid"=>7,"title"=>"节点8"),
    array("id"=>13,"fid"=>8,"title"=>"节点13"),
    array("id"=>17,"fid"=>22,"title"=>"节点17"),
    array("id"=>2,"fid"=>13,"title"=>"节点2"),
    array("id"=>24,"fid"=>13,"title"=>"节点24"),
    array("id"=>19,"fid"=>13,"title"=>"节点19"),
    array("id"=>56,"fid"=>13,"title"=>"节点56"),
);

$oTree = new Tree($rsTree,"id","fid");
//my_print_line($oTree->mRsTree);
//my_print_line($oTree->GetTrackNodes( 3,0,array('id','title') ) );
//my_print_line($oTree->GetTrackNodes( 7,1) );
//my_print_line($oTree->GetLeafNodes( 7,array('id','title')) );
//my_print_line($oTree->GetLeafNodes( 22) );
//my_print_line($oTree->GetLevelNodes(1) );
//my_print_line($oTree->GetChildNodes(22,array('id','title') ) );
//my_print_line($oTree->GetParentNodes(22) );
?>

<?php
//print_r 增强
function my_print_line($rs,$level=1)
{
    if( !is_array($rs) )
        return $rs;
    
    $str  = "<font color='#0000FF'>array</font>(";
    if($level == 1) $str .= "<br>";

    foreach($rs AS $i=>$r){
        $str .= " <font color='#FF00F0'>[{$i}]</font>=>".my_print_line($r,$level+1);
    }

    if($level == 1) $str .= "<br>";
    $str .= ")<br>";
    
    if($level > 1) return $str;
    echo "<pre>{$str}</pre>";
}
?>