[分享]PHP实现树的递归展示
原文博客地址: http://blog.csdn.net/lgg201/article/details/7973971
用法:
usage: php tree-display.php <tree deepth>
$ php tree-display.php 3 name-00000001[1]┇ ┠ name-00000002[2]┇ ┇ ┠ name-00000003[3]┇ ┇ ┠ name-00000004[4]┇ ┇ ┗ name-00000005[5]┇ ┠ name-00000006[6]┇ ┇ ┠ name-00000007[7]┇ ┇ ┠ name-00000008[8]┇ ┇ ┗ name-00000009[9]┇ ┗ name-00000010[10]┇ ┠ name-00000011[11]┇ ┠ name-00000012[12]┇ ┗ name-00000013[13]┠ name-00000014[14]┇ ┠ name-00000015[15]┇ ┇ ┠ name-00000016[16]┇ ┇ ┠ name-00000017[17]┇ ┇ ┗ name-00000018[18]┇ ┠ name-00000019[19]┇ ┇ ┠ name-00000020[20]┇ ┇ ┠ name-00000021[21]┇ ┇ ┗ name-00000022[22]┇ ┗ name-00000023[23]┇ ┠ name-00000024[24]┇ ┠ name-00000025[25]┇ ┗ name-00000026[26]┗ name-00000027[27] ┠ name-00000028[28] ┇ ┠ name-00000029[29] ┇ ┠ name-00000030[30] ┇ ┗ name-00000031[31] ┠ name-00000032[32] ┇ ┠ name-00000033[33] ┇ ┠ name-00000034[34] ┇ ┗ name-00000035[35] ┗ name-00000036[36] ┠ name-00000037[37] ┠ name-00000038[38] ┗ name-00000039[39]resource usage[level: 3, node number: 39]: clock time: 0.001967s system cpu: 0.000169s user cpu: 0.001013s memory usage: 7208 byte
<?php/** * 无限级(受尾节点描述算法限制, 详见tree_parse注释)递归菜单 * author: selfimpr * blog: http://blog.csdn.net/lgg201 * mail: lgg860911@yahoo.com.cn */define('MAX_NODES', 3); /* 最大子节点数 */define('MAX_NODE_INDEX', MAX_NODES - 1); /* 子节点最大索引值 */define('NAME_FMT', 'name-%08d'); /* 节点内容输出格式串 *//* 树节点数据结构 */define('K_ID', 'id');define('K_NAME', 'name');define('K_CHILD', 'children');/* 输出构造时使用的拼装字符 */define('PREFIX_TOP', '┏'); /* 第一层第一个节点的标识符 */define('PREFIX_BOTTOM', '┗'); /* 每一个父节点的最后一个子节点的标识符 */define('PREFIX_MIDDLE', '┠'); /* 所有非上面两种情况的节点的标识符 */define('PREFIX_LINE', '┇'); /* 祖先节点的连线符 */define('SPACE', ' '); /* 空白占位(所有尾节点不显示连线符) */define('WIDE_SPACE', str_repeat(SPACE, 4)); /* 宽的空白占位, 为了让树的层次清晰 *//** * data_build * 构造一个节点 * @param mixed $id 节点id * @param mixed $is_leaf 是否叶子 * @access public * @return void */function node_build($id, $is_leaf = FALSE) { return array( K_ID => $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 < 1 ) return ; $is_leaf = $level == 1; $i = -1; $next_level = $level - 1; while ( ++ $i < MAX_NODES ) { $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 << ($level - $i) ? SPACE : PREFIX_LINE); while ( ++ $i < $level ) $string .= WIDE_SPACE . ($is_last & 1 << ($level - $i) ? SPACE : PREFIX_LINE); $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) < 1 ) return ; $max_index = count($datas) - 1; /* 处理本层的所有节点 */ foreach ( $datas as $i => $data ) { /* 当前节点及所有祖先是否尾节点标记 */ $tmp_is_last = $is_last << 1 | 1 & $i == $max_index; /* 输出当前节点 */ node_out($string, $data, $level, $i, $tmp_is_last); /* 如果有子节点, 递归子节点 */ if ( is_array($data[K_CHILD]) && !empty($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 $info[$type . '.tv_sec'] + $info[$type . '.tv_usec'] / 1000000;}/* 输出资源使用情况 */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 <tree deepth>\n", $cmd); exit;}/* 测试入口函数 */function run() { global $argc, $argv; if ( $argc != 2 || intval($argv[1]) < 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: */