Heim >php教程 >php手册 >无限递归树展示

无限递归树展示

WBOY
WBOYOriginal
2016-06-13 10:52:181170Durchsuche

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

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel:PHP的错误类型Nächster Artikel:Deciphering Magic Methods in PHP