PHP对树的操作类

本类为phpe.net的原创,此处收藏过来和大家分享,一起学习和讨论,希望可以抛砖引玉,启发出更多的思路。

功能描述: 根据原二维数组可以转换成类似树的二维数组,也可转换为真实的树型数组,可以随意截取一颗树,提供添加结点和删除结点的方法,并提供打印到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>\r\n";
        
}
        
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());
/***/

?>
You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
One Response
  1. enartery says:

    怎么又错误了

Leave a Reply

Your email address will not be published. Required fields are marked *

*
To prove you're a person (not a spam script), type the security word shown in the picture. Click on the picture to hear an audio file of the word.
Anti-spam image