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)

    怎么又错误了

  2. how to get help in windows 10 says:
    May 31, 2019 at 7:04 am  (Quote)

    Hey! This is kind of off topic but I need some guidance from an established blog.
    Is it very hard to set up your own blog? I’m not very techincal but I can figure things out pretty quick.
    I’m thinking about creating my own but I’m not sure where to
    start. Do you have any ideas or suggestions?
    Appreciate it

  3. gamefly free trial says:
    May 31, 2019 at 10:05 am  (Quote)

    hey there and thank you for your info – I have certainly picked
    up something new from right here. I did however expertise some technical points using
    this web site, as I experienced to reload the site a lot of times previous to I
    could get it to load properly. I had been wondering if your web hosting is OK?
    Not that I’m complaining, but sluggish loading instances times will very frequently affect your placement in google and could damage your
    high-quality score if ads and marketing with Adwords.
    Well I am adding this RSS to my e-mail and could look out for a lot more of your respective fascinating content.
    Make sure you update this again soon.

  4. gamefly free trial says:
    June 3, 2019 at 12:46 am  (Quote)

    Pretty section of content. I just stumbled upon your weblog and in accession capital to
    assert that I get in fact enjoyed account your blog posts.
    Any way I will be subscribing to your augment and even I achievement you access consistently quickly.

  5. gamefly free trial says:
    June 4, 2019 at 8:08 pm  (Quote)

    Hello mates, pleasant article and good urging commented here, I am actually enjoying by these.

  6. playstation 4 pro games says:
    June 8, 2019 at 7:02 pm  (Quote)

    If some one needs to be updated with latest
    technologies therefore he must be pay a visit this web page and be up to date every day.

  7. plenty of fish dating site says:
    June 22, 2019 at 11:19 am  (Quote)

    WOW just what I was looking for. Came here by searching
    for plenty of fish dating site

  8. http://tinyurl.com/y3et7rjm says:
    July 1, 2019 at 10:50 pm  (Quote)

    Spot on with this write-up, I truly think this amazing site needs far more attention. I’ll probably
    be back again to read through more, thanks for the information!

  9. quest bars cheap says:
    July 11, 2019 at 7:16 am  (Quote)

    My relatives always say that I am wasting my time here at
    net, except I know I am getting knowledge every day by reading thes nice articles or reviews.

  10. how to get help in windows 10 says:
    July 20, 2019 at 8:09 pm  (Quote)

    I could not refrain from commenting. Perfectly written!

  11. natalielise says:
    July 22, 2019 at 10:07 pm  (Quote)

    Hi! I just wanted to ask if you ever have any trouble with hackers?
    My last blog (wordpress) was hacked and I ended up losing several weeks of
    hard work due to no backup. Do you have any solutions to prevent
    hackers? natalielise plenty of fish

  12. dating site says:
    July 31, 2019 at 3:35 am  (Quote)

    Simply wish to say your article is as amazing. The clarity on your put up is simply spectacular and that i could think you’re knowledgeable in this
    subject. Well with your permission allow me to take hold of your RSS feed
    to keep up to date with forthcoming post. Thank you
    1,000,000 and please continue the gratifying work.

  13. plenty of fish says:
    July 31, 2019 at 6:11 pm  (Quote)

    I read this paragraph fully on the topic of the resemblance of most up-to-date and previous technologies,
    it’s amazing article.

  14. plenty of fish says:
    August 1, 2019 at 12:05 am  (Quote)

    I blog frequently and I really thank you for
    your content. Your article has really peaked my interest.
    I’m going to book mark your website and keep checking for new information about
    once a week. I opted in for your RSS feed as well.

  15. pof https://natalielise.tumblr.com says:
    August 2, 2019 at 11:13 am  (Quote)

    Just want to say your article is as astounding. The clearness in your post is just excellent and i could assume
    you’re an expert on this subject. Fine with your permission let me to grab your
    RSS feed to keep updated with forthcoming post.
    Thanks a million and please continue the rewarding work.
    plenty of fish natalielise

  16. quest bars cheap says:
    September 6, 2019 at 3:34 pm  (Quote)

    Everything is very open with a very clear clarification of the issues.
    It was really informative. Your site is very helpful.

    Many thanks for sharing!

  17. minecraft games says:
    September 19, 2019 at 1:08 am  (Quote)

    Wow that was strange. I just wrote an extremely long comment but after I clicked submit my comment didn’t show up.
    Grrrr… well I’m not writing all that over again. Regardless, just wanted to say excellent blog!

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

«
»