站长论坛

标题: PHP树类 [打印本页]

---

作者: tznktg    时间: 2007-10-4 16:43
标题: PHP树类
<?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 .= "|    ";
                        }
                       
                        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());
/***/
?>

---

欢迎光临 站长论坛 (http://www.tzlink.com/bbs/)

Powered by Discuz! X3.2