Нужна помощь по рекурсии PHP для создания древовидной структуры

Question

Вот структура таблицы, которую я имею:

CREATE TABLE menu (
  menuid int(11) NOT NULL AUTO_INCREMENT,
  menuname varchar(100) NOT NULL DEFAULT '',
  menulink varchar(100) NOT NULL DEFAULT '',
  menuparentId int(11) NOT NULL DEFAULT '0',
  menuhasChild smallint(1) NOT NULL DEFAULT '0',
  menustatus smallint(1) NOT NULL DEFAULT '1',
  menuorder int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (menuid)
)

Я использую рекурсивную функцию, чтобы создать структуру меню из этого, и здесь происходит сбой:

function categoriesTree($id=0){    
    $s = "SELECT * FROM menu  WHERE menuparentId = '".$id."' 
        ORDER BY menuorder, menuid ";
    $rid = $this->db->query($s)->result_array();
    $treeArray = array();
    foreach($rid as $row){
        $treeArray[$row['menuid']] = $row;
        if($row['menuhasChild']==1){
            $treeArray[$row['menuid']] = $this->categoriesTree(); //results in Fatal error: Maximum function nesting level of '100' reached, aborting!
        }
    }
 retrun $treeArray;
 }

Данный метод являетсямодели в классе модели CodeIgniter.Есть ли лучший способ создать дерево?

Answer 1

Да, есть намного лучший способ.Так называемый модифицированный алгоритм обхода дерева предзаказов.Вы можете найти много информации, прибегнув к этому, и я уверен в переполнении стека.

Преимущества состоят в том, что вы можете получить целое поддерево, используя всего 1 запрос.ВЫБОРЫ будут быстрыми, но модификации тяжелее.

Answer 2

Я думаю, что вы должны добавить идентификатор в качестве параметра в вызове вашей функции.

$this->categoriesTree($row['menuid']) 

В противном случае вы каждый раз вызываете функцию одинаково.

Answer 3

Вот лучший пример. Это исправленная форма первого ответа.

 function categoriesTree($id=0) {
    $s = "SELECT * FROM design_menu  WHERE menuparentId = '" . $id . "' 
    ORDER BY menuorder, menuid ";
    $rid = $this->db->query($s)->result_array();
    $treeArray = array();

    foreach ($rid as $row) {

        $treeArray[$row['menuid']] = $row;
        if ($row['menuhasChild'] == 1) {
            $treeArray[$row['menuname']] = $this->categoriesTree($row['menuid']); //results in Fatal error: Maximum function nesting level of '100' reached, aborting!
        }
    }
    return $treeArray;
}

Answer 4

Создание меню с использованием древовидных структур с родительскими / дочерними отношениями на основе реляционной базы данных очень громоздко. Реляционные базы данных ужасны для древовидных структур. Они требуют, чтобы вы написали много бизнес-логики просто для представления ваших данных в удобочитаемом формате. Обновление меню с дополнительными функциями требует добавления к этому рекурсивному циклу ... оно может стать очень сложным, в зависимости от сложности вашего меню. Не говоря уже о том, что в конечном итоге вы захотите все это кэшировать, потому что цикл становится довольно дорогим в вычислительном отношении при больших нагрузках. Подумайте об этом, если у вас есть 5 пунктов меню верхнего уровня, 2 дочерних элемента и каждый дочерний элемент, имеющий n самих дочерних элементов, вы будете выполнять 16 операторов SQL.

Могу ли я предложить другое решение: JSON . Раньше у меня была такая таблица меню, и теперь я просто сохраняю ее представление в формате JSON в базе данных SQL (хотя даже это можно кэшировать в памяти / файловой системе). Меню JSON гораздо более компактно с точки зрения пространства, логично просто читать и не требует возиться с родительскими и дочерними идентификаторами. Это работает намного лучше с PHP (json_encode / decode), превращающим меню в собственный массив. Как и в случае с Javascript, что важно, например, если вы выполняете ajax-вызовы, чтобы изменить порядок своего меню в приложении. Иерархические древовидные структуры - это то, что хорошо в JSON. Это также избавляет от необходимости отслеживать ваш «порядок меню» (потому что порядок массива задается внутренне)

Пример формата меню следующий:

{
["en": "Home", "fr": "Accueil"],
["en": "Settings", "fr": "Paramètres", "child": 
    {
        ["en": "Email", "fr": "Email", "role": "EmailUser"]
    }
}

Как вы можете видеть, он действительно предлагает дополнительные функциональные возможности, такие как «роль», привязанная к пункту меню. Добавление такого рода функциональности не требует нового рекурсивного кода или изменений в вашей схеме SQL. Это действительно намного более гибко.

Итак, на самом деле я не отвечаю на вопрос, но, надеюсь, предоставлю какой-то совет / понимание того, что, по моему мнению, является лучшим решением этой проблемы.

Answer 5

<?php
require_once ROOT_PATH . '/lib/dao/MySQLClass.php';
require_once ROOT_PATH . '/lib/confs/Conf.php';
/**
 * Generate HTML for multi-dimensional menu from MySQL database
 * with ONE QUERY and WITHOUT RECURSION
 * @author J. Bruni
 */
//print_r($_SESSION['symfony/user/sfUser/culture']);die;
class MenuBuilder
{
    /**
     * MySQL connection
     */
    var $conn;

    /**
     * Menu items
     */
    var $items = array();

    /**
     * HTML contents
     */
    var $html  = array();

        //var $culture = $_SESSION['symfony/user/sfUser/culture'];
        var $culture;
        var $columnName;
    /**
     * Create MySQL connection
     */
    function MenuBuilder()
    {
        $conf = new Conf();
            $db=new MySQLClass($conf);
           $this->conn = mysql_connect($db->myHost .':'.$db->myHostPort, $db->userName, $db->userPassword);

           $this->culture=$_SESSION['language'];

    }

    /**
     * Perform MySQL query and return all results
     */
    function fetch_assoc_all( $sql )
    {
                if($this->culture=="en"){
                $this->columnName='sm_mnuitem_name';

                }else{
                    $this->columnName='sm_mnuitem_name_'.$this->culture;
                }
                //die(print_r($_SESSION));
                if($_SESSION['user']=="USR001"){
                $query="SELECT sm_mnuitem_id, sm_mnuitem_parent, ".$this->columnName.", sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY sm_mnuitem_parent, sm_mnuitem_position;";
                }
                else{
                    $query="select * from hs_hr_sm_mnuitem m left join hs_hr_sm_mnucapability c on m.sm_mnuitem_id=c.sm_mnuitem_id left join hs_hr_users u on u.sm_capability_id=c.sm_capability_id where u.id='".$_SESSION['user']."' ORDER BY m.sm_mnuitem_parent, m.sm_mnuitem_position;";
                }
        //$result = mysql_query("SELECT sm_mnuitem_id, sm_mnuitem_parent, ".$this->columnName.", sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY sm_mnuitem_parent, sm_mnuitem_position;",$this->conn);
                $result = mysql_query($query,$this->conn);

        if ( !$result ){

            return false;

                }

        $assoc_all = array();

        while( $fetch = mysql_fetch_assoc( $result ) ){
            $assoc_all[] = $fetch;
                }
                //die(print_r($assoc_all));
        mysql_free_result( $result );

        return $assoc_all;

    }

    /**
     * Get all menu items from database
     */
    function get_menu_items()
    {
        // Change the field names and the table name in the query below to match tour needs
        $sql = 'SELECT sm_mnuitem_id, sm_mnuitem_parent, sm_mnuitem_name, sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY s_mnuitem_parent, sm_mnuitem_position;';

        return $this->fetch_assoc_all( $sql );
    }

    /**
     * Build the HTML for the menu
     */
    function get_menu_html( $root_id = 0 )
    {
        $this->html  = array();
        $this->items = $this->get_menu_items();
                //print_r($this->items);die("");

        foreach ( $this->items as $item )
            $children[$item['sm_mnuitem_parent']][] = $item;

        // loop will be false if the root has no children (i.e., an empty menu!)
        $loop = !empty( $children[$root_id] );

        // initializing $parent as the root
        $parent = $root_id;
        $parent_stack = array();

        // HTML wrapper for the menu (open)
                //$this->html[] = '<div>';
        $this->html[] = '<ul id="qm0" class="qmmc">';

        while ( $loop && ( ( $option = each( $children[$parent] ) ) || ( $parent > $root_id ) ) )
        {
            if ( $option === false )
            {
                $parent = array_pop( $parent_stack );

                // HTML for menu item containing childrens (close)
                $this->html[] = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 ) . '</ul>';
                $this->html[] = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ) . '</li>';
            }
            elseif ( !empty( $children[$option['value']['sm_mnuitem_id']] ) )
            {
                $tab = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 );

                // HTML for menu item containing childrens (open)
                $url="";
                if($option['value']['sm_mnuitem_webpage_url']=="#"){
                    $url="javascript:void(0);";
                }else{
                    $url=$option['value']['sm_mnuitem_webpage_url'];
                }        

                $this->html[] = sprintf(
                    '%1$s<li><a class="qmparent" href="%2$s">%3$s</a>',
                    $tab,   // %1$s = tabulation
                    //$option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $url,
                    $option['value'][$this->columnName]   // %3$s = title
                );
                $this->html[] = $tab . "\t" . '<ul>';

                array_push( $parent_stack, $option['value']['sm_mnuitem_parent'] );
                $parent = $option['value']['sm_mnuitem_id'];
            }
            else{

                // HTML for menu item with no children (aka "leaf")
                             if($_SESSION['user']!="USR001"){
                            if($option['value']['sm_mnuitem_webpage_url']!="#"){

                $this->html[] = sprintf(
                    '%1$s<li><a target="rightMenu" href="%2$s">%3$s</a></li>',
                    str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ),   // %1$s = tabulation
                    $option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $option['value'][$this->columnName]   // %3$s = title
                );
                            }
                             }else{
                                 $this->html[] = sprintf(
                    '%1$s<li><a target="rightMenu" href="%2$s">%3$s</a></li>',
                    str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ),   // %1$s = tabulation
                    $option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $option['value'][$this->columnName]   // %3$s = title
                );
                             }
                        }
        }

        // HTML wrapper for the menu (close)
        $this->html[] = '</ul>';
                //$this->html[] = '</div>';

        return implode( "\r\n", $this->html );
    }
}





?>

Answer 6

Строка:

$treeArray[$row['menuid']] = $this->categoriesTree();

должна быть:

$treeArray[$row['menuid']] = $this->categoriesTree($row['menuid']);