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 .= “_idkey]. “\”>”. $str. $val[$catnamekey]. “\r\n”;
}
return $options;
}

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