$id,
k_name => sprintf(name_fmt, $id),
k_child => $is_leaf ? null : array(),
);
}
/**
* tree_build
* 构造一棵树(树中每个节点的子节点数由max_nodes确定)
* @param mixed $datas 要返回的树引用
* @param mixed $id 起始id
* @param mixed $level 树的层级
* @access public
* @return void
*/
function tree_build(&$datas, &$id, $level) {
if ( $level $is_leaf = $level == 1;
$i = -1;
$next_level = $level - 1;
while ( ++ $i $data = node_build($id ++, $is_leaf);
if ( !$is_leaf )
tree_build($data[k_child], $id, $next_level);
array_push($datas, $data);
}
}
/**
* node_str
* 输出一个节点自身的信息
* @param mixed $string 返回结果的字符串(引用传值)
* @param mixed $data 节点数据
* @access public
* @return void
*/
function node_str(&$string, $data) {
$string .= sprintf(' %s[%d]', $data[k_name], $data[k_id]);
}
/**
* node_sign
* 输出一个节点的标志符号
* @param mixed $string 返回结果的字符串(引用传值)
* @param mixed $level 当前深度
* @param mixed $i 当前节点在父节点中的索引(下标)
* @access public
* @return void
*/
function node_sign(&$string, $level, $i) {
switch ( $i ) {
case 0:
$string .= $level == 0 ? prefix_top : prefix_middle;
break;
case max_node_index:
$string .= prefix_bottom;
break;
default:
$string .= prefix_middle;
break;
}
}
/**
* node_prefix
* 输出一个节点的前缀
* @param mixed $string 返回结果的字符串(引用传值)
* @param mixed $level 当前深度
* @param mixed $is_last 当前节点(含)所有祖先节点是否尾节点标记
* @access public
* @return void
*/
function node_prefix(&$string, $level, $is_last) {
if ( $level > 0 ) {
$i = 0;
/* 前缀格式: 父级连线 [宽空白符 父级连线 ...] 宽空白符 */
$string .= ($is_last & 1 while ( ++ $i $string .= wide_space . ($is_last & 1 $string .= wide_space;
}
}
/**
* node_out
* 输出一个节点
* @param mixed $string 返回结果的字符串(引用传值)
* @param mixed $data 要处理的节点数据
* @param mixed $level 节点深度
* @param mixed $i 节点在父节点中的索引(下标)
* @param mixed $is_last 当前节点(含)所有祖先节点是否尾节点标记
* @access public
* @return void
*/
function node_out(&$string, $data, $level, $i, $is_last) {
/* 处理前缀字符串: 祖先的连接符及空白 */
node_prefix($string, $level, $is_last);
/* 处理本节点的标识符号 */
node_sign($string, $level, $i);
/* 处理本节点数据信息 */
node_str($string, $data);
/* 追加换行 */
$string .= \n;
}
/**
* tree_parse
* 输出一棵树
* 1. 由于使用了整型的$is_last作为祖先是否尾节点的标记, 所以最多支持php_int_max的深度
* 2. 如果需要扩展, 修正$is_last的数据类型及校验方法即可
* @param mixed $string 返回结果的字符串(引用传值)
* @param mixed $datas 要处理的树数据
* @param int $level 当前处理的深度
* @param int $is_last 当前深度所有祖先是否尾节点标记
* @access public
* @return void
*/
function tree_parse(&$string, $datas, $level = 0, $is_last = 0) {
if ( !is_array($datas) || count($datas) $max_index = count($datas) - 1;
/* 处理本层的所有节点 */
foreach ( $datas as $i => $data ) {
/* 当前节点及所有祖先是否尾节点标记 */
$tmp_is_last = $is_last /* 输出当前节点 */
node_out($string, $data, $level, $i, $tmp_is_last);
/* 如果有子节点, 递归子节点 */
if ( is_array($data[k_child]) && !emptyempty($data[k_child]) )
tree_parse($string, $data[k_child], $level + 1, $tmp_is_last);
}
}
/* 计算实际节点数 */
function n_node($n, $s) {
$sum = 0;
while ( $n > 0 )
$sum += pow($s, $n --);
return $sum;
}
/* 计算ruage时间 */
function ru_time($info, $type) {
return floatval(sprintf('%d.%d', $info[$type . '.tv_sec'], $info[$type . '.tv_usec']));
}
/* 输出资源使用情况 */
function resource_usage($lv, $nodes, $cb, $ce, $mb, $me, $rb, $re) {
printf(\nresource usage[level: %d, node number: %d]: \n%20s%0.6fs\n%20s%0.6fs\n%20s%0.6fs\n%20s%d byte\n,
$lv, $nodes,
'clock time: ', $ce - $cb,
'system cpu: ', ru_time($re, 'ru_stime') - ru_time($rb, 'ru_stime'),
'user cpu: ', ru_time($re, 'ru_utime') - ru_time($rb, 'ru_utime'),
'memory usage: ', $me - $mb);
}
/* 用法 */
function usage($cmd) {
printf(usage: \n%s \n, $cmd);
exit;
}
/* 测试入口函数 */
function run() {
global $argc, $argv;
if ( $argc != 2 || intval($argv[1]) usage($argv[0]);
$datas = array();
$id = 1;
$string = '';
$level = intval($argv[1]);
/* 初始构造测试树 */
tree_build($datas, $id, $level);
$clock_begin = microtime(true);
$memory_begin = memory_get_usage();
$rusage_begin = getrusage();
/* 解析树 */
tree_parse($string, $datas);
$rusage_end = getrusage();
$memory_end = memory_get_usage();
$clock_end = microtime(true);
/* 输出结果 */
echo $string . \n;
resource_usage($level, n_node($level, max_nodes),
$clock_begin, $clock_end,
$memory_begin, $memory_end,
$rusage_begin, $rusage_end);
}
/* 执行入口函数 */
run();
/*
* local variables:
* tab-width: 4
* c-basic-offset: 4
* indent-tabs-mode: t
* end:
*/
http://www.bkjia.com/phpjc/477981.htmlwww.bkjia.comtruehttp://www.bkjia.com/phpjc/477981.htmltecharticle[php] ?php /** * 无限级(受尾节点描述算法限制, 详见tree_parse注释)递归菜单 * author: selfimpr * blog: http://blog.csdn.net/lgg201 * mail: lgg860911@yahoo.com.cn...