PHP树类

tznktg · 发表于 2007-10-4 16:43:52

<?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());
/***/
?>

		自动登录	找回密码
密码			注册

全国各地医院查询	重量转换换算	RGB颜色查询	交通标志大全	各类快递查询
简体繁体转换	黄金价格实时走势	万年历查询	实时汇率转换	列车时刻查询
在线翻译工具	CSS中文手册	HTML学习教程	MySQL中文手册	JavaScript中文手册
PHP安全基础手册	PHP5面向对象编程教程	正则表达式系统教程	SQL Server精华	Apache 2.2 中文手册
DOS命令全集指南	windows脚本技术中文版	股票行情查询	历史上的今天	邮编区号查询
长度转换换算	货币汇率转换	常用电话号码	体育彩票查询	手机位置查询
域名Whois信息查询	谷歌PR值查询	台州网站建设	台州网站开发	台州域名注册
天气预报查询	长度转换换算器	在线电子地图	车牌号码查询	中国百家姓查询

PHP树类

相关帖子