PHP对树的操作类

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

功能描述: 根据原二维数组可以转换成类似树的二维数组,也可转换为真实的树型数组,可以随意截取一颗树,提供添加结点和删除结点的方法,并提供打印到HTML的select控件的方法


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 .= “\r\n”;
}
return $options;
}

public function html_select($name, $options, $size = 1)
{
$selectstr = “”;
$selectstr .= ‘‘;
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());
/***/
?>

1 thought on “PHP对树的操作类”

  1. 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.

  2. 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

  3. 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.

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