PHP XML - Как построить дерево узлов XML, которые находятся на одном уровне с родительскими дочерними отношениями

Question

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

<Categories>

<Category>
  <Id>1</Id>
  <Name>Parent 1</Name>
  <ParentId>1</ParentId>
  <ParentName>Parent 1</ParentName>
</Category>
<Category>
  <Id>2</Id>
  <Name>Child 1</Name>
  <ParentId>1</ParentId>
  <ParentName>Parent 1</ParentName>
</Category>
<Category>
  <Id>3</Id>
  <Name>Child 2</Name>
  <ParentId>1</ParentId>
  <ParentName>Parent 1</ParentName>
</Category>
<Category>
  <Id>8</Id>
  <Name>Grand Child 1 -1</Name>
  <ParentId>2</ParentId>
  <ParentName>Child 1</ParentName>
</Category>

<Category>
  <Id>12</Id>
  <Name>Parent 2</Name>
  <ParentId>12</ParentId>
  <ParentName>Parent 2</ParentName>
</Category>

<Category>
  <Id>15</Id>
  <Name>Child 2-1</Name>
  <ParentId>12</ParentId>
  <ParentName>Parent 2</ParentName>
</Category>

  </Categories>
</CategoryList>

Я хочу прочитать этот XML-файл (я знаю, как его читать), но я не могу отформатировать его следующим образом ... Как бы я получитьвсе узлы, которые являются самыми старшими родителями и являются дочерними по отношению к этим родительским узлам (используя рекурсию или что-то еще)

<ul>
<li>Parent 1
    <ul>
        <li> Child 1
            <ul>
                <li>Grand Child 1 -1</li>
            </ul>

        </li>
        <li> Child 2</li>
    </ul>

</li>
<li>Parent 2
    <ul>
        <li>Child 2-1 </li>
    </ul>

</li>

</ul>

Пожалуйста, любая помощь будет принята с благодарностью ....

Редактировать * То, что я сделал до сих пор ...

$xml= simplexml_load_string('myxmlstring');

get_categories($xml, 0);

function get_categories($xml, $id) {

    if ($id==0) 
        $Categories = $xml->xpath('Categories/Category[ParentId=Id]');
    else
        $Categories = $xml->xpath('Categories/Category[ParentId='.$id.' and Id!='.$id.']');

    echo '<ul id="catlist'.$id.'">';
    foreach($Categories as $Category) {
        echo "<li>ID: " . $Category->Id . "--Name: " . $Category->Name;
        get_categories($xml, $Category->Id);
        echo "</li>";

    }
    echo "</ul>";
}

Теперь я просто хочу подтвердить, что это оптимальное решение.или кто-то может прийти с лучшей идеей ...

Answer 1

Спасибо, kirilloid .... это было очень полезно ... Я использую код с некоторыми изменениями ... XML от curl, и я знаю, что ParentName является чрезмерным, но я не могу его контролировать.Вот окончательный код ....

$childrenReferences = array();
$rootNodesIDs = array();
$xmlNodes = array();

$dom = new DOMDocument;
$dom->loadXML($xml);

$Categories = $dom->getElementsByTagName('Category');
$length = $Categories->length;

for ($i = 0; $i < $length; $i++) {
    $cat = $Categories->item($i);           //Get the DOMNode 
    $id = $cat->getElementsByTagName('Id')->item(0)->nodeValue;
    $parentId = $cat->getElementsByTagName('ParentId')->item(0)->nodeValue;
    $xmlNodes[$id] = $cat;      

    if ($parentId == $id) {
        $rootNodesIDs []= $id;
        continue;
    }

    if (array_key_exists($parentId, $childrenReferences)) {
        $childrenReferences[$parentId] []= $id;         
    } else {
        $childrenReferences[$parentId] = array($id);
    }
}

function out_nodes($rootids) {
    global $childrenReferences, $xmlNodes;

    echo "<ul>";
    foreach ($rootids as $id) {
        $cat = $xmlNodes[$id];
        echo "<li>ID: " . $cat->getElementsByTagName('Id')->item(0)->nodeValue . "--Name: " . $cat->getElementsByTagName('Name')->item(0)->nodeValue;
        if (array_key_exists($id, $childrenReferences)) { // intermediate node
            out_nodes($childrenReferences[$id]);
        }
        echo "</li>";
    }
    echo "</ul>";
}

ob_start();
out_nodes($rootNodesIDs);
ob_end_flush();

Answer 2

ParentName является чрезмерным, достаточно указать только родительский идентификатор.

Поскольку вы выполняете поиск для каждого узла, время выполнения будет O (N ² ), где N - количество узлов.

Однако есть возможность сделать это за линейное время: сначала пройти по данным и построить древовидную структуру (или несколько), а затем пройти по этой структуре и вывести выходные узлы в соответствии с ней.

Буферизация вывода также является хорошим вариантом здесь.

// init
$childrenReferences = array();
$rootNodes = array();
$xmlNodes = array();

// gathering structure
$cats = $xml->getElementsByTagName('Category');
for ($i = 0; $i < $cats->length; $i++) {
    $cat = $cats[$i];
    $id = $children->Id;
    $parentId = $cat->ParentId;
    $xmlNodes[$id] = $cat;
    if ($parentId == $id) {
        $rootNodes []= $id;
        continue;
    }
    if (array_key_exists($parentId, $childrenReferences)) {
        $childrenReferences[$parentId] []= $id;
    } else {
        $childrenReferences[$parentId] = array($id);
    }

}

// output
function out_nodes($nodes) {
    global $childrenReferences, $xmlNodes; // this is not required since php 5.3 or something about
    echo "<ul>";
    foreach ($nodes as $id) {
        $cat = $xmlNodes[$id];
        echo "<li>ID: " . $cat->Id . "--Name: " . $cat->Name;
        if (array_key_exists($id, $childrenReferences)) { // intermediate node
            out_nodes($childrenReferences[$id]);
        }
        echo "</li>";
    }
    echo "</ul>";
}

ob_start();
out_nodes($rootNodes);
ob_end_flush();

Код может не работать или даже не компилироваться, но вы поняли.