PHP对树的操作类

By
31
May 2006

本类为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());
/***/
?>
Category: PHP / Zend, 技术交流
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:
    June 22, 2010 at 1:04 pm  (Quote)

    怎么又错误了

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

«
»