无限递归树展示

[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     $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:
 */