Home > Backend Development > PHP Tutorial > Infinite recursion tree display_PHP tutorial

Infinite recursion tree display_PHP tutorial

WBOY
Release: 2016-07-13 17:53:58
Original
1072 people have browsed it

[php]
/**
* Infinite level (limited by the tail node description algorithm, see tree_parse comment for details) recursive menu
* author: selfimpr
* blog: http://blog.csdn.net/lgg201
* mail: lgg860911@yahoo.com.cn
​*/

define('MAX_NODES', 3); /* Maximum number of child nodes */
define('MAX_NODE_INDEX', MAX_NODES - 1); /* Maximum index value of child nodes */
define('NAME_FMT', 'name-%08d'); /* Node content output format string */

/* Tree node data structure */
define('K_ID', 'id');
define('K_NAME', 'name');
define('K_CHILD', 'children');

/* Output the assembly characters used in construction */
define('PREFIX_TOP',                                                                                                                                                                                                                                                                                       through define('PREFIX_BOTTOM', '┗'); /* The identifier of the last child node of each parent node */
define('PREFIX_MIDDLE', '┠'); /* Identifiers of all nodes that are not in the above two cases */
define('PREFIX_LINE', '┇'); /* The ligature of the ancestor node */
define('SPACE',             ' ');                                                                                                                                                                                                                         define('WIDE_SPACE', str_repeat(SPACE, 4)); /* Wide blank placeholder, in order to make the hierarchy of the tree clear */


/**
* data_build
* Construct a node
* @param mixed $id Node id
* @param mixed $is_leaf Whether it is a 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
* Construct a tree (the number of child nodes of each node in the tree is determined by MAX_NODES)
* @param mixed $datas The tree reference to be returned
* @param mixed $id Starting ID
* @param mixed $level The level of the tree
* @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
* Output a node’s own information
 * @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
* Output the glyph of a node
* @param mixed $string Return the string of the result (pass by value)
* @param mixed $level Current depth
* @param mixed $i The index (subscript) of the current node in the parent node
* @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
* Output the prefix of a node
* @param mixed $string Return the string of the result (pass by value)
* @param mixed $level Current depth
* @param mixed $is_last Whether all ancestor nodes of the current node (including) have tail node tags
* @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
* Output a node
* @param mixed $string Return the string of the result (pass by value)
* @param mixed $data The node data to be processed
* @param mixed $level Node depth
* @param mixed $i The index (subscript) of the node in the parent node
* @param mixed $is_last Whether all ancestor nodes of the current node (including) have tail node tags
* @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;
/* Process all nodes in this layer */
foreach ( $datas as $i => $data ) {
             /* Whether the current node and all ancestors are marked as tail nodes */
$tmp_is_last = $is_last << 1 | 1 & $i == $max_index;
/* Output the current node */
Node_out($string, $data, $level, $i, $tmp_is_last);
           /* If there are child nodes, recurse the child nodes */
If ( is_array($data[K_CHILD]) && !emptyempty($data[K_CHILD]) )
Tree_parse($string, $data[K_CHILD], $level + 1, $tmp_is_last);
}  
}

/* Calculate the actual number of nodes */
function n_node($n, $s) {
$sum = 0;
while ( $n > 0 )
$sum += pow($s, $n --);
Return $sum;
}
/* Calculate ruage time */
function ru_time($info, $type) {
Return floatval(sprintf('%d.%d', $info[$type . '.tv_sec'], $info[$type . '.tv_usec']));
}
/* Output resource usage */
function resource_usage($lv, $nodes, $cb, $ce, $mb, $me, $rb, $re) {
Printf("nresource usage[level: %d, node number: %d]: n%20s%0.6fsn%20s%0.6fsn%20s%0.6fsn%20s%d byten",
         $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);
}
/* Usage */
function usage($cmd) {
Printf("usage: n%s n", $cmd);
exit;
}

/* Test entry function */
function run() {
global $argc, $argv;

If ( $argc != 2 || intval($argv[1]) < 1 )
usage($argv[0]);


$datas = array();
$id = 1;
$string = '';
$level = intval($argv[1]);

/* Initial construction of test tree */
Tree_build($datas, $id, $level);

$clock_begin = microtime(TRUE);
$memory_begin = memory_get_usage();
$rusage_begin = getrusage();
/* Parse tree */
Tree_parse($string, $datas);
$rusage_end = getrusage();
$memory_end = memory_get_usage();
$clock_end = microtime(TRUE);

/* Output results */
echo $string . "n";

Resource_usage($level, n_node($level, MAX_NODES),
$clock_begin, $clock_end,
         $memory_begin, $memory_end, 
         $rusage_begin, $rusage_end);
}

/* Execute entry function */
run();
/*
* Local variables:
* tab-width: 4
* c-basic-offset: 4
* indent-tabs-mode: t
* End:
*/

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/477981.htmlTechArticle[php] ?php /** * Infinite level (limited by the tail node description algorithm, see tree_parse comment for details) Recursive menu * author: selfimpr * blog: http://blog.csdn.net/lgg201 * mail: lgg860911@yahoo.com.cn...
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template