Implementation of PHP Infinitus classification (without using recursion), php recursion_PHP tutorial

PHP Infinitus classification implementation (without recursion), PHP recursion

Infinitus classification is often used in development, such as: department structure, article classification. The difficulty of Infinitus classification lies in "output" and "query", such as

• Output the article classification into
  list form;
• Find articles contained in all categories under category A.

1. Implementation principle

In the article "Infinite Classification Implementation Ideas", several common implementation methods are introduced, each with advantages and disadvantages. Among them, the "improved preorder traversal tree" data structure is convenient for output and query, but it is somewhat complicated in mobile classification and general understanding.

2. Data structure

id	fid	title
1	0	中国
2	1	江苏
3	1	安徽
4	8	江阴
5	3	芜湖
6	3	合肥
7	3	蚌埠
8	2	无锡

<code><?php
    $list = array(
        array('id'=>1, 'fid'=>0, 'title' => '中国'), 
        array('id'=>2, 'fid'=>1, 'title' => '江苏'),
        array('id'=>3, 'fid'=>1, 'title' => '安徽'),
        array('id'=>4, 'fid'=>8, 'title' => '江阴'),
        array('id'=>5, 'fid'=>3, 'title' => '芜湖'),
        array('id'=>6, 'fid'=>3, 'title' => '合肥'),
        array('id'=>7, 'fid'=>3, 'title' => '蚌埠'),
        array('id'=>8, 'fid'=>8, 'title' => '无锡')
    );
?></code>

Each category is "concatenated" through the parent category id (i.e. fid) to form a classification tree. One thing worth noting when performing concatenation: the fid of category A cannot be the id of its subcategory.

The most commonly used algorithm when using this data structure for output is "recursion". Friends who are familiar with the PHP language must know that PHP is not good at recursion, and the number of recursions is limited (about 100 times, depending on the operating system and configuration) ).

Since all recursion can be implemented using loops, this article has written a set of functions for "infinite level" classification based on the characteristics of the PHP language, which is more efficient than recursive implementation

3. Output ul list form

Output the above data as the following HTML

<code><ul>
    <li class="first-child">
        <div>江苏</div>
        <ul>
            <li class="first-child last-child">
                <div>无锡</div>
                <ul>
                    <li class="first-child last-child">
                        <div>江阴</div>
                    </li>
                </ul>
            </li>
        </ul>
    </li>
    <li class="last-child">
        <div>安徽</div>
        <ul>
            <li class="first-child"><div>芜湖</div></li>
            <li><div>合肥</div></li>
            <li class="last-child"><div>蚌埠</div></li>
        </ul>
    </li>
</ul>
</code>

This HTML structure is very convenient to use on the front end (using JavaScript and CSS to construct a collapsible tree). The specific implementation procedure is as follows:

<code><ul><?php get_tree_ul($list, 1); ?></ul></code>

4. Output option list form

<code><select>
<option value="2">江苏</option>
<option value="8">    无锡</option>
<option value="4">        江阴</option>
<option value="3">安徽</option>
<option value="5">    芜湖</option>
<option value="6">    合肥</option>
<option value="7">    蚌埠</option>
</select></code>

The specific implementation procedures are as follows:

<code><select>
<?php
    // get_tree_option()返回数组，并为每个元素增加了&ldquo;深度&rdquo;（即depth）列，直接输出即可
    $options = get_tree_option($list, 1); 
    foreach($options as $op) {
        echo '<option value="' . $op['id'] .'">' . str_repeat(" ", $op['depth'] * 4) . $op['title'] . '<;/option>';
    }
?>
<;/select></code>

5. Find all subcategories of a certain category

<code><?php
    $children = get_tree_child($list, 0);
    echo implode(',', $children);    // 输出：1,3,2,7,6,5,8,4
?></code>

6. Find all parent categories of a certain category

<code><?php
    $children = get_tree_parent($list, 4);
    echo implode(',', $children);    //8, 2, 10
?></code>

7. Related functions

<code><?php
function get_tree_child($data, $fid) {
    $result = array();
    $fids = array($fid);
    do {
        $cids = array();
        $flag = false;
        foreach($fids as $fid) {
            for($i = count($data) - 1; $i >=0 ; $i--) {
                $node = $data[$i];
                if($node['fid'] == $fid) {
                    array_splice($data, $i , 1);
                    $result[] = $node['id'];
                    $cids[] = $node['id'];
                    $flag = true;
                }
            }
        }
        $fids = $cids;
    } while($flag === true);
    return $result;
}

function get_tree_parent($data, $id) {
    $result = array();
    $obj = array();
    foreach($data as $node) {
        $obj[$node['id']] = $node;
    }    

    $value = isset($obj[$id]) ? $obj[$id] : null;    
    while($value) {
        $id = null;
        foreach($data as $node) {
            if($node['id'] == $value['fid']) {
                $id = $node['id'];
                $result[] = $node['id'];
                break;
            }
        }
        if($id === null) {
            $result[] = $value['fid'];
        }
        $value = isset($obj[$id]) ? $obj[$id] : null;
    }
    unset($obj);
    return $result;
}

function get_tree_ul($data, $fid) {
    $stack = array($fid);
    $child = array();
    $added_left = array();
    $added_right= array();
    $html_left     = array();
    $html_right    = array();
    $obj = array();
    $loop = 0;
    foreach($data as $node) {
        $pid = $node['fid'];
        if(!isset($child[$pid])) {
            $child[$pid] = array();
        }
        array_push($child[$pid], $node['id']);
        $obj[$node['id']] = $node;
    }

    while (count($stack) > 0) {    
        $id = $stack[0];
        $flag = false;
        $node = isset($obj[$id]) ? $obj[$id] : null;
        if (isset($child[$id])) {
            $cids = $child[$id];
            $length = count($cids);
            for($i = $length - 1; $i >= 0; $i--) {
                array_unshift($stack, $cids[$i]);
            }
            $obj[$cids[$length - 1]]['isLastChild'] = true;
            $obj[$cids[0]]['isFirstChild'] = true;
            $flag = true;
        }
        if ($id != $fid && $node && !isset($added_left[$id])) {
            if(isset($node['isFirstChild']) && isset($node['isLastChild']))  {
                $html_left[] = '<li class="first-child last-child">';
            } else if(isset($node['isFirstChild'])) {
                $html_left[] = '<li class="first-child">';
            } else if(isset($node['isLastChild'])) {
                $html_left[] = '<li class="last-child">';
            } else {
                $html_left[] = '<li>';
            }            
            $html_left[] = ($flag === true) ? "<div>{$node['title']}</div><ul>" : "<div>{$node['title']}</div>";
            $added_left[$id] = true;
        }    
        if ($id != $fid && $node && !isset($added_right[$id])) {
            $html_right[] = ($flag === true) ? '</ul></li>' : '</li>';
            $added_right[$id] = true;
        }

        if ($flag == false) {
            if($node) {
                $cids = $child[$node['fid']];
                for ($i = count($cids) - 1; $i >= 0; $i--) {
                    if ($cids[$i] == $id) {
                        array_splice($child[$node['fid']], $i, 1);
                        break;
                    }
                } 
                if(count($child[$node['fid']]) == 0) {
                    $child[$node['fid']] = null;
                }
            }
            array_push($html_left, array_pop($html_right));
            array_shift($stack);
        }
        $loop++;
        if($loop > 5000) return $html_left;
    }
    unset($child);
    unset($obj);
    return implode('', $html_left);
}

function get_tree_option($data, $fid) {
    $stack = array($fid);
    $child = array();
    $added = array();
    $options = array();
    $obj = array();
    $loop = 0;
    $depth = -1;
    foreach($data as $node) {
        $pid = $node['fid'];
        if(!isset($child[$pid])) {
            $child[$pid] = array();
        }
        array_push($child[$pid], $node['id']);
        $obj[$node['id']] = $node;
    }

    while (count($stack) > 0) {    
        $id = $stack[0];
        $flag = false;
        $node = isset($obj[$id]) ? $obj[$id] : null;
        if (isset($child[$id])) {
            for($i = count($child[$id]) - 1; $i >= 0; $i--) {
                array_unshift($stack, $child[$id][$i]);
            }
            $flag = true;
        }
        if ($id != $fid && $node && !isset($added[$id])) {
            $node['depth'] = $depth;
            $options[] = $node;
            $added[$id] = true;
        }
        if($flag == true){
            $depth++;
        } else {
            if($node) {
                for ($i = count($child[$node['fid']]) - 1; $i >= 0; $i--) {
                    if ($child[$node['fid']][$i] == $id) {
                        array_splice($child[$node['fid']], $i, 1);
                        break;
                    }
                } 
                if(count($child[$node['fid']]) == 0) {
                    $child[$node['fid']] = null;
                    $depth--;
                }
            }
            array_shift($stack);
        }
        $loop++;
        if($loop > 5000) return $options;
    }
    unset($child);
    unset($obj);
    return $options;
}
?></code>

php recursion problem (infinitus classification)

Foreach itself is equivalent to judgment. When the $arr array is not empty, foreach will traverse and recursively access the child nodes. However, for leaf nodes, the $arr array is empty and will not be foreached at all. At this time, it is directly returned. clear?

php recursion problem, want to display data according to Infinitus classification style

First decode json into an array, use the json_decode function. Note that you must add the second parameter, otherwise it will return an object. The next step is recursion. This is the simplest recursion that just needs to be traversed one by one.
The following is the complete code:
$data= json_decode($str,true);$options = getChildren($data);function getChildren($parent,$deep=0) {foreach($parent as $ row) {$data[] = array("id"=>$row['id'], "name"=>$row['name'],"pid"=>$row['parentid' ],'deep'=>$deep);if ($row['childs']) {$data = array_merge($data, getChildren($row['childs'], $deep+1));}} return $data;}?>
The above code has been tested and passed. The rendering is as follows

http://www.bkjia.com/PHPjc/831802.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/831802.htmlTechArticleImplementation of PHP Infinitus classification (without using recursion), PHP recursive Infinitus classification is often used in development, such as : Department structure, article classification. The difficulty of Infinitus classification lies in output and search...