структура данных для дерева обхода в PHP?

Изменить: Хорошо, я изучил это еще немного. Я думаю, что в номенклатуре произошла путаница. Вы не ищете структуру данных для трансверального дерева в PHP. Вы хотите использовать дерево в качестве структуры данных в PHP и хотите восстановить данные из этого дерева с помощью метода, называемого модифицированным алгоритмом обхода дерева предварительного порядка .

Цитата:

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

Речь идет о хранении иерархических данных в PHP и MySQL. В PHP мы можем использовать простое дерево. Проблема в том, что хранить дерево в плоской базе данных MySQL непросто. Один из вариантов - взять PHP и извлечь из него список смежности. По сути, это список каждого элемента и его родителей. У этого способа есть свои недостатки.

Другой метод - извлечь информацию из дерева PHP, описывающую вложенные наборы, которые могут быть составлены из иерархических данных. Чтобы получить эту информацию из дерева PHP, нам необходимо использовать модифицированный алгоритм обхода дерева предварительного порядка . Это метод бега вверх и вниз по дереву, чтобы извлечь из него определенную информацию.

Используем ли мы модель списка смежности или модифицированный обход дерева предварительного порядка для получения информации, мы используем одно и то же дерево PHP. Разница заключается в том, как мы получаем информацию из дерева и как мы храним информацию в MySQL.Код для извлечения информации из MySQL уже находится на цитируемой вами странице . Чтобы синхронизировать данные между PHP и MySQL, вам просто нужно использовать методы MySQL, описанные на этой странице, и класс дерева PHP.

Для этого я создал класс в PHP, который хранит дерево. Он использует узлы. Каждый узел можно рассматривать как корень полного дерева, поскольку из каждого узла можно получить доступ к полному поддереву. Просто было легче отделить узел от дерева, и это привело к меньшим накладным расходам.

Важной частью класса является метод showAdjacency . Это запускает дерево с использованием модифицированного обхода дерева предварительного порядка и отображает количество lft и rgt для каждого имени, которое позволяет вам хранить данные в MySQL как вложенный набор.

Вы также можете отобразить дерево, чтобы вы могли его визуализировать. В этом классе отсутствует метод удаления. Когда вы его реализуете, вы должны передать потомков удаленного узла родительскому узлу. Может, сделаю это позже.

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

      // The modified preorder tree traversal.
    private function showAdjacency($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
              // On the way down the tree, we get lft.
            $left = ++$spaces;                
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $spaces = $this->showAdjacency($child, $spaces);                      
                }
            }
        }
          // On the way back up, we get rgt.
        $right = ++$spaces;
        echo "$left - $right - $root->data <br/>";                
        return $spaces;
    }

Очевидно, вы можете хранить $ root-> data, $ rgt и $ lft в массиве, который вы используете для синхронизации с вашей базой данных.

Вот весь класс. После занятия я создаю дерево, используя образцы данных из страницы, которую вы связали с , и выводю значения lft и rgt, а также визуализацию дерева.

Вы можете запустить код на Codepad

<?php  
  // Class defintions and methods:
  // It's easier to use separate nodes. Each node still points to an entire and complete subtree.
class Node
{
    public $data;
    public $next = array();
}

  // A first try at creating a tree with any number of branches from its nodes
  // by Peter Ajtai - feel free to use and modify
class Tree
{
    // The root
    private $root;
    public function __construct()
    {
        $this->root = NULL;
    }

      // The public wrapper. 
      // This is needed because we must start the recursive functions
      // at the root, and we do not want to give public access to root.
      // I am not familiar w overloading in PHP, maybe __set should be used for this
    public function insertPub($data, $parent)
    {
        $root =& $this->root;
        $this->insert($root, $data, $parent);
    }

    private function insert(&$root, $data, $parent)
    {

          // Create the root of the entire tree if no parent is passed in        
        if (!$root && !$parent)
        {
            $root = new Node;
            $temp =& $root;
            $temp->data = $data;
            // Create space for next insertion
            $temp->next[] = NULL;                     
        } else if ($root->data == $parent)
        {

              // Add data as a child if we're at the parent, and we're done.
              // Find the empty node to insert at
            foreach($root->next as &$child)
            {
                  // Insert at the first (and only) NULL
                if (!$child)
                {
                    $child = new Node;
                    $temp =& $child;
                    $temp->data = $data;                        
                    // Create space for next insertion
                    $temp->next[] = NULL;
                }
            }
              // Create space for the next insertion
            $root->next[] = NULL;
        } else
        {
              // Keep searching for the parent as default behavior.
            foreach($root->next as $child)
            {
                if ($child)
                {
                    $this->insert($child, $data, $parent);
                }
            }
        }
    }
      // Public wrapper for the display function.
    public function showAdjPub()
    {
        echo "The neighbors:<br/><br/>";
        $root =& $this->root;
        $this->showAdjacency($root, 0);
        echo "<br/>";
    }

      // The display function.
    private function showAdjacency($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
            $left = ++$spaces;                
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $spaces = $this->showAdjacency($child, $spaces);                      
                }
            }
        }
        $right = ++$spaces;
        echo "$left - $right - $root->data <br/>";                
        return $spaces;
    }
      // Public wrapper for the display function.
    public function showAllPub()
    {
        echo "The tree:<br/><br/>";
        $root =& $this->root;
        $this->showAll($root, 0);
        echo "<br/>";
    }

      // The display function.
    private function showAll($root, $spaces)
    {
          // Print the data first
        if ($root)
        {
            for ($i=0; $i < $spaces; ++$i)
                echo "---> ";
            echo "$root->data <br/>";
            ++$spaces;
            foreach( $root->next as $child)
            {                    
                if ($child)
                {
                    $this->showAll($child, $spaces);
                }
            }
        }
    }        
}

  // Create a new instance of the tree
$myTree = new Tree;

  // Insert the data into the tree.    
  // The following data would be retrieved using MySQL
$name = 'Electronics'; $parent = NULL;
$myTree->insertPub($name, $parent);
$name = 'Televisions'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'Tube'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);    
$name = 'Lcd'; $parent = 'Televisions';
$myTree->insertPub($name, $parent); 
$name = 'Plasma'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);    
$name = 'Portable Electronics'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);    
$name = 'MP3 Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    
$name = 'Flash'; $parent = 'MP3 Players';
$myTree->insertPub($name, $parent);    
$name = 'CD Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    
$name = '2 Way Radios'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);    

  // Display adjacency
$myTree->showAdjPub();

  // Show hierarchy    
$myTree->showAllPub();      
?>

PS: Хранить данные в PHP во вложенных массивах, как вы предложили, было бы очень сложно. В приведенном выше классе, если элемент данных удаляется, дерево изменяется (включая добавление целых поддеревьев и т. Д.), Значения lft и rgt будут по-прежнему извлечены правильно.

Если вы используете массивы для хранения информации, вам будет очень сложно удалить элементы, у которых есть и родительские, и дочерние элементы, а обновление значений lft и rgt будет очень сложным. Наконец, добавление в массив больших наборов (поддеревьев) также будет чрезвычайно трудным.

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