功能描述： 根据原二维数组可以转换成类似树的二维数组，也可转换为真实的树型数组，可以随意截取一颗树，提供添加结点和删除结点的方法，并提供打印到HTML的select控件的方法
<?php 
class PHPTree 
{ 
    /*** 
     * @project PHPTree Program Demo 
     * @license GPL 
     * @author 勾伯今 trooman@sina.com, somyth@gmail.com 
     * @package  
     * @file 
     * @date 2006-5-25 
     * @version 1.1 
     * @last modified  
      
     * 定义 PHPTree 类 
     * 
     * 根据原二维数组可以转换成类似树的二维数组，也可转换为真实的树型数组，可以随意截取一颗树，并提供打印到HTML的select控件的方法 
     * 
     * 易于理解，使用简单，功能强大 
     * 
     ***/ 
      
    public $_idkey; //定义数据表关键字的键名 
    public $_pidkey; //定义数据表的父亲字段的键名 
    public $_catnamekey; //定义分类的类名（的键名) 
    public $_isordered = false; //定义原数据是否按层级排序 
    private $_rootid; //定义根结点 
    private $_tmparr = array(); //定义一个数组用来接受传进来的数组 
    private $_tree = array(); //定义一个数组用以生成树 
     
    function __construct($arr) 
    { 
        /***$arr如同 
        $ar = array(  
                        array('id' => 1, 'pid' => 0, 'classname' => 'A') 
                    ) 
        调用时如果不指定键名程序将自动搜索键名，顺序是:id,pid,classname 
        ***/        
        $this->_tmparr     = $arr; 
        $keys              = $this->getkeys(); 
        $this->_idkey      = $keys[0]; 
        $this->_pidkey     = $keys[1]; 
        $this->_catnamekey = $keys[2]; 
         
        $this->_rootid     = $this->get_rootid(); 
        $this->_tree       = $this->make_tree(); 
    } 
         
    public function getkeys() 
    { 
        $arr = $this->_tmparr[0]; 
        return array_keys($arr); 
    } 
     
    public function get_rootid() 
    { 
        //寻找根结点，这是个很有意思的问题，随便给你一个二维数组，你能确定它可以构成一颗树吗？？？本方法为你解决 
        //算法是根据“父”的“父”是否存在，如果存在记录在一个数组中，最后确定此数组的array_count_values个数 
        //如果大于1，则原数组不完整，返回false 
        //如果等于1，则是完整的，返回此数组第一个值即可 
         
        //本方法可带一个参数$array数组 
        $numargs = func_num_args();     
        $tmparr = ($numargs == 0) ? $this->_tmparr : func_get_arg(0); 
        $size = count($tmparr); 
         
        $arr = array(); 
         
        foreach($tmparr as $key => $val) 
        { 
            for( $i=($this->_isordered) ? ($key+1):0; $i<$size; $i++ ) 
            { 
                $isfind = false; 
                if($tmparr[$i][$this->_idkey] == $val[$this->_pidkey]) 
                { 
                    $isfind = true; 
                    break; 
                } 
  
                if($i==$size-1 && $isfind == false) 
                { 
                    $arr[count($arr)] = $val[$this->_pidkey]; 
                } 
            } 
        } 
         
        if( count(array_count_values($arr)) > 1 ) 
        { 
            return false; //不完整，不可能得到树 
        } 
         
        unset($tmparr); 
        return $arr[0]; //返回根结点 
    } 
     
    //$this->_isordered为true表示已经按层级排序，否则没有 
    public function make_tree()  
    { 
        //本方法可带一个参数$root_id，即根结点 
        $numargs = func_num_args();     
        $root_id = ($numargs == 0) ? $this->_rootid : func_get_arg(0); 
         
        if($root_id = $this->_rootid && !empty($this->_tree)) 
        { 
            return $this->_tree; 
        } 
         
        $arr = $this->_tmparr;     
        $tree = array(); //目标数组 
        $index = array(); //索引数组（堆栈） 
        $arr_size = count($arr); 
         
  
        //$arr_size2 = count($arr, COUNT_RECURSIVE); //此方法没用到$arr_size2 
        $vlayer = 1; //定义$tree的初始层级为1 
        $i = 0; 
         
        while($i < $arr_size) 
        {     
            if($arr[$i][$this->_pidkey] == $root_id && empty($arr[$i]['yes'])) 
            { 
                $tree[count($tree)] = $arr[$i]; 
                $tree[count($tree)-1]['vlayer'] = $vlayer; 
                $vlayer++; 
                 
                $index[count($index)][$this->_pidkey] = $arr[$i][$this->_pidkey]; 
     
                $arr[$i]['yes'] = 1; 
                $root_id = $arr[$i][$this->_idkey]; //改变当前根结点 
                 
                //如果未排序按默认算法使$i=-1，因为后面的$i++ 还要计算一次$i，如果已排序，继续往下执行     
                if($this->_isordered == false) 
                { 
                    $i = -1; 
                } 
            } 
     
            if($i == $arr_size-1) 
            { 
                if(count($index) == 0) 
                { 
                    break; 
                } 
                 
                $i = ($this->_isordered == false) ? 0:$index[count($index) -1]['index']; //如果未排序按默认算法$i回到0，否则按最优算法直接往下继续 
                 
                $root_id = $index[count($index) -1][$this->_pidkey]; 
                array_pop($index); 
                $vlayer--;     
            } 
             
            if(count($tree) == $arr_size)  
            { 
                break; 
            } 
             
            $i++; 
        } 
         
        unset($arr); 
        unset($index); 
        unset($arr_size); 
        return $this->_tree = $tree; 
         
    } 
     
     
    public function make_subtree() 
    {     
        $numargs = func_num_args(); 
        if($numargs == 0 || func_get_arg(0) == $this->_rootid) 
        { 
            return $this->_tree; 
        } 
         
        $root_id = func_get_arg(0); //第一个参数 
        $tree    = ($numargs == 1) ? $this->_tree:func_get_arg(1); //第2个参数 
  
        $subtree = array(); 
        foreach($tree as $key => $val) 
        { 
            if($val[$this->_idkey] == $root_id) 
            { 
                $subtree[0] = $val; 
                $subtree[0]['vlayer'] = 1; 
                $src_vlayer = $val['vlayer']; 
                $isok = false; 
                $size = count($tree); 
                 
                for($i=$key+1; $i<$size; $i++) 
                { 
                    if($tree[$i]['vlayer'] <= $src_vlayer) 
                    { 
                        $isok = true; 
                        break; 
                    } 
                    $subtree[count($subtree)] = $tree[$i]; 
                    $subtree[count($subtree)-1]['vlayer'] = $subtree[count($subtree)-2]['vlayer'] + 1; 
                } 
            } 
             
            if($isok == true) 
            { 
                break; 
            } 
        } 
         
        return $subtree; 
    } 
     
     
    public function make_truetree($arr) 
    { 
        //生成一颗真实的树 
        if(!array_key_exists('vlayer', $arr[0])) 
        { 
            return false; 
        } 
         
        $index = array(); 
        $truetree = array(); 
        $j = 0; 
        $index[0]['index_str'] = '$truetree'; 
                 
        foreach($arr as $key => $val) 
        { 
            $str = $index[$j]['index_str']; 
            eval('$counts = count('. $str. ');'); 
            eval( $str. '[$counts] = $val;' ); 
            eval( $str. '[$counts]['child'] = array();' ); 
         
            if($arr[$key+1]['vlayer'] > $val['vlayer']) 
            { 
                $j++; 
                $index[$j]['index_str'] = $index[$j-1]['index_str']. "[". $counts. "]['child']"; 
            } 
             
            if($arr[$key+1]['vlayer'] < $val['vlayer']) 
            { 
                array_pop($index); 
                $j--; 
            } 
        } 
         
        unset($index); 
        unset($j); 
        return $truetree; 
    } 
     
     
    public function addnode($arr) 
    { 
        //添加结点到数组中 
        $counts = count($this->_tmparr); 
        foreach($arr as $key => $val) 
        { 
            $this->_tmparr[$counts] = $val; 
            $counts++; 
        } 
         
        //并且添加到当前树中 
        foreach($arr as $key => $val) 
        { 
            $pos = 0; 
            foreach($this->_tree as $key2 => $val2) 
            { 
                if($val[$this->_idkey] > 0 && $val[$this->_idkey] == $val2[$this->_pidkey]) 
                { 
                    $tmp[0] = $val; 
                    $this->_tree = array_merge($tmp, $this->_tree); 
                    break; 
                } 
                 
                if($val[$this->_pidkey] == $val2[$this->_idkey]) 
                { 
                    $pos = $key2+1; 
                    $merge_l = array_slice($this->_tree, 0, $pos); 
                    $merge_r = array_slice($this->_tree, $pos); 
                    $tmp[0] = $val; 
                    $merge = array_merge($merge_l, $tmp); 
                    $merge = array_merge($merge, $merge_r); 
                    $this->_tree = $merge; 
                    break; 
                } 
            } 
        } 
    } 
  
  
    public function delnode($id) 
    { 
        //注，只能删除叶子结点 
        $is_leaf = false; 
        foreach($this->_tree as $key => $val) 
        { 
            if($val[$this->_idkey] == $id) 
            { 
                if(!isset($this->_tree[$key+1]) || $this->_tree[$key+1]['vlayer'] <= $val['vlayer']) 
                { 
                    $is_leaf = true; //是叶子结点 
                    array_splice($this->_tree, $pos, 1); 
                } 
                break; 
            } 
        }     
         
        if($is_leaf) 
        { 
            foreach($this->_tmparr as $key => $val) 
            { 
                if($val[$this->_idkey] == $id) 
                { 
                    array_splice($this->_tmparr, $key, 1); 
                    break; 
                } 
            } 
        } 
         
        return $is_leaf; 
    } 
     
     
    public function get_leafs() 
    { 
        //遍历叶子结点 
        //本方法可带一个参数$tree数组（已排序好的虚拟树） 
        $numargs = func_num_args();     
        $tree = ($numargs == 0) ? $this->_tree : func_get_arg(0); 
         
        $leafs = array(); 
        foreach($tree as $key => $val) 
        { 
            if(!isset($tree[$key+1]) || $tree[$key+1]['vlayer'] <= $val['vlayer']) 
            { 
                $leafs[] = $val; 
            } 
        } 
        return $leafs;         
    } 
     
    public function html_options() 
    { 
        $numargs = func_num_args(); 
        if($numargs == 0) 
        { 
            $tree = $this->_tree; 
            $catnamekey = $this->_catnamekey; 
        } 
        elseif($numargs == 1) 
        { 
            $tree = func_get_arg(0); 
            $catnamekey = $this->_catnamekey; 
        } 
        else 
        { 
            $tree = func_get_arg(0); 
            $catnamekey = func_get_arg(1); 
        } 
         
         
        if(!is_array($tree)) 
        { 
            return false; 
        } 
         
        $options = ""; 
        foreach($tree as $key => $val) 
        { 
            $layer = $val['vlayer']-1; 
            $str = ""; 
            for($i=1; $i<$layer; $i++) 
            { 
                $str .= "|&nbsp;&nbsp;&nbsp;&nbsp;"; 
            } 
             
            if($layer >= 1) 
            { 
                $str .= "|----"; 
            } 
  
            $options .= "<option value="". $val[$this->_idkey]. "">". $str. $val[$catnamekey]. "</option>rn"; 
        } 
        return $options; 
    } 
     
    public function html_select($name, $options, $size = 1) 
    { 
        $selectstr = ""; 
        $selectstr .= '<select name="'. $name. '" id="'. $name. '" size="'. $size. '">'; 
        $selectstr .= $options; 
        $selectstr .= '</select>'; 
        return $selectstr; 
    } 
} 
/***类到此结束**************************************************************************************/ 
  
  
  
  
  
  
/***以下是演示*************************************************************************************** 
$ar = array(  
           array('id' => 1, 'pid' => 0, 'classname' => 'A'),  
           array('id' => 7, 'pid' => 0, 'classname' => 'B'), 
           array('id' => 8, 'pid' => 0, 'classname' => 'C'), 
           array('id' => 2, 'pid' => 1, 'classname' => 'G'), 
           array('id' => 9, 'pid' => 1, 'classname' => 'H'), 
           array('id' => 3, 'pid' => 7, 'classname' => 'I'),  
           array('id' => 4, 'pid' => 8, 'classname' => 'F'),  
           array('id' => 5, 'pid' => 4, 'classname' => 'D'),  
           array('id' => 6, 'pid' => 5, 'classname' => 'E')  
); 
  
  
  
$ar2 = array(           
           array('id' => 3, 'pid' => 7, 'classname' => 'I'),  
           array('id' => 4, 'pid' => 8, 'classname' => 'F'),  
           array('id' => 5, 'pid' => 4, 'classname' => 'D'),  
           array('id' => 1, 'pid' => 0, 'classname' => 'A'),  
           array('id' => 7, 'pid' => 0, 'classname' => 'B'), 
           array('id' => 8, 'pid' => 0, 'classname' => 'C'), 
           array('id' => 2, 'pid' => 1, 'classname' => 'G'), 
           array('id' => 9, 'pid' => 1, 'classname' => 'H'), 
           array('id' => 6, 'pid' => 5, 'classname' => 'E')  
); 
  
  
/*** 
//对于已按层级排序好的数组$ar 
echo "对于已按层级排序好的数组$ar n"; 
$cats = new Cats($ar); 
$cats->_idkey = 'id'; 
$cats->_pidkey = 'pid'; 
$cats->_isordered = true; 
print_r($cats->make_tree()); 
print_r($cats->make_tree(8)); 
/***/ 
  
  
/*** 
//对于未按层级排序的数组$ar2 
echo "对于未按层级排序的数组$ar2 n"; 
$cats2 = new Cats($ar2); 
print_r($cats2->make_tree()); 
print_r($cats2->make_tree(8)); 
/***/ 
  
/*** 
//如果是一个未排序的数组，你却标记已排序，将得不到正确的结果，如 
echo "如果是一个未排序的数组，你却标记已排序，将得不到正确的结果，如 n"; 
$cats3 = new Cats($ar2); 
$cats3->_isordered = true; // 
print_r($cats3->make_tree()); 
/***/ 
  
/*** 
echo "生成子树及输出到html的select演示 n"; 
$cats4 = new Cats($ar2); 
$tree = $cats4->make_tree(); 
print_r($tree); 
$subtree = $cats4->make_subtree(8); 
print_r($subtree); 
  
$options = $cats4->html_options($subtree,'classname'); //或者$cats4->html_options($subtree) 
echo $cats4->html_select('xxx',$options, 6); 
/***/ 
  
  
/*** 
echo "从一颗子树中再截取一颗子树 n"; 
$cats5 = new Cats($ar2); 
print_r($cats5->make_subtree(4, $cats5->make_subtree(8))); //从一颗子树中再截取一颗子树 
  
echo "根据一颗虚树生成一颗实树 n"; 
print_r( $cats5->make_truetree( $cats5->make_tree() ) ); //根据一颗虚树生成一颗实树 
/***/ 
  
/*** 
$cats6 = new Cats($ar2); 
$y[0]['id'] = 0; 
$y[0]['pid'] = -1; 
$y[0]['classname'] = 'This is error'; 
  
$y[3]['id'] = 20; 
$y[3]['pid'] = 9; 
$y[3]['classname'] = "for"; 
  
$y[4]['id'] = 21; 
$y[4]['pid'] = 20; 
$y[4]['classname'] = "you"; 
$cats6->addnode($y); 
print_r($cats6->make_tree()); 
print_r($cats6->make_truetree($cats6->make_tree())); 
$cats6->delnode(21); 
print_r($cats6->make_tree()); 
/***/ 
?>