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

WBOY
Release: 2016-07-13 10:24:00
Original
1253 people have browsed it

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>
    Copy after login

    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>
    Copy after login

    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>
    Copy after login

    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>
    Copy after login

    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>
    Copy after login

    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>
    Copy after login

    6. Find all parent categories of a certain category

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

    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>
    Copy after login

    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


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

    www.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...
Related labels:
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
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!