PHP implements infinite classification (without using recursion)_php skills

Infinite-level classification is often used in development, such as department structure and article classification. The difficulty of infinite 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
  There are several common implementation methods, 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

  

  <&#63;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' => '无锡')
   );
  &#63;>
  

  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

  <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>
  

  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:

  <ul><&#63;php echo get_tree_ul($list, 1); &#63;></ul>
  

  4. Output option list form
  

  <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>

  The specific implementation procedures are as follows:

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

  5. Find all subcategories of a certain category
  

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

  6. Find all parent categories of a certain category
  

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

  7. Related functions
  

  <&#63;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]) &#63; $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]) &#63; $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]) &#63; $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) &#63; "<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) &#63; '</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]) &#63; $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;
  }
  &#63;>
  

  The above introduction is about how to implement Infinitus classification in PHP without using recursion. I hope it will be helpful to everyone's learning.