将一系列父子关系转换为分层树？

我有一堆名字 – 父母对，我想变成尽可能less的边angular树结构。 举例来说，这些可能是配对：

Child : Parent H : G F : G G : D E : D A : E B : C C : E D : NULL 

哪些需要转化成（a）叶状树（s）：

 D ├── E │ ├── A │ │ └── B │ └── C └── G ├── F └── H 

我想要的最终结果是嵌套的一组<ul>元素，每个<li>包含子元素的名称。

配对中没有不一致（孩子是自己的父母，父母是孩子的孩子等），所以可能会做出一堆优化。

在PHP中，如何从包含child =>父对的数组转到一组嵌套的<ul> s？

我有一种感觉，涉及到recursion，但是我还不够清醒。

Answer 1

这需要一个非常基本的recursion函数来将子/父对parsing为树结构，并使用另一个recursion函数将其打印出来。 只有一个函数就足够了，但为了清晰，这里有两个函数（在这个答案的末尾可以find一个组合的函数）。

首先初始化子/父对的数组：

 $tree = array( 'H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null ); 

然后，将该数组parsing为分层树结构的函数：

 function parseTree($tree, $root = null) { $return = array(); # Traverse the tree and search for direct children of the root foreach($tree as $child => $parent) { # A direct child is found if($parent == $root) { # Remove item from tree (we don't need to traverse this again) unset($tree[$child]); # Append the child into result array and parse its children $return[] = array( 'name' => $child, 'children' => parseTree($tree, $child) ); } } return empty($return) ? null : $return; } 

还有一个遍历树的函数来打印一个无序列表：

 function printTree($tree) { if(!is_null($tree) && count($tree) > 0) { echo '<ul>'; foreach($tree as $node) { echo '<li>'.$node['name']; printTree($node['children']); echo '</li>'; } echo '</ul>'; } } 

而实际使用情况：

 $result = parseTree($tree); printTree($result); 

以下是$result的内容：

 Array( [0] => Array( [name] => D [children] => Array( [0] => Array( [name] => G [children] => Array( [0] => Array( [name] => H [children] => NULL ) [1] => Array( [name] => F [children] => NULL ) ) ) [1] => Array( [name] => E [children] => Array( [0] => Array( [name] => A [children] => NULL ) [1] => Array( [name] => C [children] => Array( [0] => Array( [name] => B [children] => NULL ) ) ) ) ) ) ) ) 

---

如果您想要更高效一些，可以将这些function合并为一个，并减less迭代次数：

 function parseAndPrintTree($root, $tree) { $return = array(); if(!is_null($tree) && count($tree) > 0) { echo '<ul>'; foreach($tree as $child => $parent) { if($parent == $root) { unset($tree[$child]); echo '<li>'.$child; parseAndPrintTree($child, $tree); echo '</li>'; } } echo '</ul>'; } } 

你只能在这样一个小的数据集上保存8次迭代，但是在更大的集合上它可以有所作为。

Answer 2

另一个function，使树（不涉及recursion，而是使用引用）：

 $array = array('H' => 'G', 'F' => 'G', ..., 'D' => null); function to_tree($array) { $flat = array(); $tree = array(); foreach ($array as $child => $parent) { if (!isset($flat[$child])) { $flat[$child] = array(); } if (!empty($parent)) { $flat[$parent][$child] =& $flat[$child]; } else { $tree[$child] =& $flat[$child]; } } return $tree; } 

返回一个像这样的分层数组：

 Array( [D] => Array( [G] => Array( [H] => Array() [F] => Array() ) ... ) ) 

可以使用recursion函数轻松地将其打印为HTML列表。

Answer 3

另一种更简单的方法是将$tree的平面结构转换为层次结构。 只需要一个临时数组来公开它：

 // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); 

这就是把层次结构变成一个multidimensional array：

 Array ( [children] => Array ( [0] => Array ( [children] => Array ( [0] => Array ( [name] => H ) [1] => Array ( [name] => F ) ) [name] => G ) [1] => Array ( [name] => E [children] => Array ( [0] => Array ( [name] => A ) [1] => Array ( [children] => Array ( [0] => Array ( [name] => B ) ) [name] => C ) ) ) ) [name] => D ) 

---

如果你想避免recursion（可能是大型结构的负担），那么输出就不那么简单了。

我一直想解决输出数组的UL / LI“难题”。 困境在于，每个项目都不知道孩子是否会跟进，或者有多less前面的元素需要closures。 在另一个答案我已经解决了，通过使用RecursiveIteratorIterator并寻找我自己的书面Iterator提供的getDepth()和其他元信息： 获取嵌套集模型到一个<ul>但隐藏“封闭”的子树 。 这个答案显示了迭代器，你很灵活。

但是这是一个预先sorting的列表，所以不适合你的例子。 此外，我一直想解决这个问题，一个标准的树结构和HTML的<ul>和<li>元素。

我想到的基本概念如下：

1. TreeNode – 将每个元素抽象为一个简单的TreeNodetypes，可以提供它的值（例如Name ）以及是否有子元素。
2. TreeNodesIterator – 能够遍历这些TreeNodes的集合（数组）的RecursiveIterator 。 这是非常简单的，因为TreeNodetypes已经知道它是否有孩子，哪些孩子。
3. RecursiveListIterator – 一个RecursiveIteratorIterator ，当它recursion迭代任何types的RecursiveIterator时，它具有所需的所有事件：
   • endIteration / endIteration – 主列表的开始和结束。
   • beginElement / endElement – 每个元素的开始和结束。
   • beginChildren / endChildren – 每个子列表的开始和结束。 这个RecursiveListIterator只以函数调用的forms提供这些事件。 子列表（通常是<ul><li>列表）在其父<li>元素中打开和closures。 因此endElement事件在相应的endChildren事件之后被触发。 这可以改变或可configuration，以扩大这个类的使用。 这些事件是作为函数调用分发给装饰器对象的，然后把事情分开。
4. ListDecorator – “decorator”类，它只是RecursiveListIterator事件的接收者。

我从主输出逻辑开始。 采取现在分层$tree数组，最终的代码如下所示：

 $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(1); printf("%s%s\n", $inset, $item->getName()); } 

首先让我们看看ListDecorator ，它简单地包装<ul>和<li>元素，并决定如何输出列表结构：

 class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } 

构造函数接受它正在处理的列表迭代器。 inset只是一个很好的缩进输出帮助函数。 其余的只是每个事件的输出函数：

  public function beginElement() { printf("%s<li>\n", $this->inset()); } public function endElement() { printf("%s</li>\n", $this->inset()); } public function beginChildren() { printf("%s<ul>\n", $this->inset(-1)); } public function endChildren() { printf("%s</ul>\n", $this->inset(-1)); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } 

考虑到这些输出函数，这又是主要的输出包装/循环，我一步步地经历它：

 $root = new TreeNode($tree); 

创build将用于开始迭代的根TreeNode ：

 $it = new TreeNodesIterator(array($root)); 

这个TreeNodesIterator是一个RecursiveIterator ，它可以对单个$root节点进行recursion迭代。 它作为一个数组传递，因为这个类需要迭代的东西，并允许与一组子节点重用，这也是一个TreeNode元素的数组。

 $rit = new RecursiveListIterator($it); 

这个RecursiveListIterator是一个提供上述事件的RecursiveIteratorIterator 。 要使用它，只需要提供一个ListDecorator （上面的类）并分配给addDecorator ：

 $decor = new ListDecorator($rit); $rit->addDecorator($decor); 

然后一切都设置为foreach并输出每个节点：

 foreach($rit as $item) { $inset = $decor->inset(1); printf("%s%s\n", $inset, $item->getName()); } 

如本例所示，整个输出逻辑封装在ListDecorator类和这个单一的foreach 。 整个recursion遍历已经被完全封装成SPLrecursion迭代器，它提供了一个堆栈过程，这意味着在内部没有recursion函数调用完成。

基于事件的ListDecorator允许您专门修改输出，并为相同的数据结构提供多种types的列表。 甚至有可能在arrays数据被封装到TreeNode改变input。

完整的代码示例：

 <?php namespace My; $tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null); // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); class TreeNode { protected $data; public function __construct(array $element) { if (!isset($element['name'])) throw new InvalidArgumentException('Element has no name.'); if (isset($element['children']) && !is_array($element['children'])) throw new InvalidArgumentException('Element has invalid children.'); $this->data = $element; } public function getName() { return $this->data['name']; } public function hasChildren() { return isset($this->data['children']) && count($this->data['children']); } /** * @return array of child TreeNode elements */ public function getChildren() { $children = $this->hasChildren() ? $this->data['children'] : array(); $class = get_called_class(); foreach($children as &$element) { $element = new $class($element); } unset($element); return $children; } } class TreeNodesIterator implements \RecursiveIterator { private $nodes; public function __construct(array $nodes) { $this->nodes = new \ArrayIterator($nodes); } public function getInnerIterator() { return $this->nodes; } public function getChildren() { return new TreeNodesIterator($this->nodes->current()->getChildren()); } public function hasChildren() { return $this->nodes->current()->hasChildren(); } public function rewind() { $this->nodes->rewind(); } public function valid() { return $this->nodes->valid(); } public function current() { return $this->nodes->current(); } public function key() { return $this->nodes->key(); } public function next() { return $this->nodes->next(); } } class RecursiveListIterator extends \RecursiveIteratorIterator { private $elements; /** * @var ListDecorator */ private $decorator; public function addDecorator(ListDecorator $decorator) { $this->decorator = $decorator; } public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0) { parent::__construct($iterator, $mode, $flags); } private function event($name) { // event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]); $callback = array($this->decorator, $name); is_callable($callback) && call_user_func($callback); } public function beginElement() { $this->event('beginElement'); } public function beginChildren() { $this->event('beginChildren'); } public function endChildren() { $this->testEndElement(); $this->event('endChildren'); } private function testEndElement($depthOffset = 0) { $depth = $this->getDepth() + $depthOffset; isset($this->elements[$depth]) || $this->elements[$depth] = 0; $this->elements[$depth] && $this->event('endElement'); } public function nextElement() { $this->testEndElement(); $this->event('{nextElement}'); $this->event('beginElement'); $this->elements[$this->getDepth()] = 1; } public function beginIteration() { $this->event('beginIteration'); } public function endIteration() { $this->testEndElement(); $this->event('endIteration'); } } class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } public function beginElement() { printf("%s<li>\n", $this->inset(1)); } public function endElement() { printf("%s</li>\n", $this->inset(1)); } public function beginChildren() { printf("%s<ul>\n", $this->inset()); } public function endChildren() { printf("%s</ul>\n", $this->inset()); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(2); printf("%s%s\n", $inset, $item->getName()); } 

Outpupt：

 <ul> <li> D <ul> <li> G <ul> <li> H </li> <li> F </li> </ul> </li> <li> E <ul> </li> <li> A </li> <li> C <ul> <li> B </li> </ul> </li> </ul> </li> </ul> </li> </ul> 

演示（PHP 5.2变体）

一个可能的变体是一个遍历任何RecursiveIterator的迭代器，并提供对所有可能发生的事件的迭代。 然后在foreach循环中的开关/ case可以处理事件。

有关：

• 带有RecursiveArrayIterator的嵌套列表
• RecursiveIteratorIterator类

Answer 4

那么，首先我要把键值对的直接数组变成一个分层数组

 function convertToHeiarchical(array $input) { $parents = array(); $root = array(); $children = array(); foreach ($input as $item) { $parents[$item['id']] = &$item; if ($item['parent_id']) { if (!isset($children[$item['parent_id']])) { $children[$item['parent_id']] = array(); } $children[$item['parent_id']][] = &$item; } else { $root = $item['id']; } } foreach ($parents as $id => &$item) { if (isset($children[$id])) { $item['children'] = $children[$id]; } else { $item['children'] = array(); } } return $parents[$root]; } 

这将可以转换一个平面数组parent_id和id到一个分层的：

 $item = array( 'id' => 'A', 'blah' => 'blah', 'children' => array( array( 'id' => 'B', 'blah' => 'blah', 'children' => array( array( 'id' => 'C', 'blah' => 'blah', 'children' => array(), ), ), 'id' => 'D', 'blah' => 'blah', 'children' => array( array( 'id' => 'E', 'blah' => 'blah', 'children' => array(), ), ), ), ), ); 

然后，只需创build一个渲染函数：

 function renderItem($item) { $out = "Your OUtput For Each Item Here"; $out .= "<ul>"; foreach ($item['children'] as $child) { $out .= "<li>".renderItem($child)."</li>"; } $out .= "</ul>"; return $out; } 

Answer 5

尽pipe亚历山大·康斯坦丁诺夫的解决scheme起初看起来并不那么容易，但在性能方面它既是天才又是指数级更好，这应该被认为是最好的答案。

感谢队友，我为你做了一个基准比较这篇文章中提出的两个解决scheme。

我有一个@ 250k的扁平树，有6个级别，我必须转换，我正在寻找一个更好的方法来避免recursion迭代。

recursion与参考：

 // Generate a 6 level flat tree $root = null; $lvl1 = 13; $lvl2 = 11; $lvl3 = 7; $lvl4 = 5; $lvl5 = 3; $lvl6 = 1; $flatTree = []; for ($i = 1; $i <= 450000; $i++) { if ($i % 3 == 0) { $lvl5 = $i; $flatTree[$lvl6] = $lvl5; continue; } if ($i % 5 == 0) { $lvl4 = $i; $flatTree[$lvl5] = $lvl4; continue; } if ($i % 7 == 0) { $lvl3 = $i; $flatTree[$lvl3] = $lvl2; continue; } if ($i % 11 == 0) { $lvl2 = $i; $flatTree[$lvl2] = $lvl1; continue; } if ($i % 13 == 0) { $lvl1 = $i; $flatTree[$lvl1] = $root; continue; } $lvl6 = $i; } echo 'Array count: ', count($flatTree), PHP_EOL; // Reference function function treeByReference($flatTree) { $flat = []; $tree = []; foreach ($flatTree as $child => $parent) { if (!isset($flat[$child])) { $flat[$child] = []; } if (!empty($parent)) { $flat[$parent][$child] =& $flat[$child]; } else { $tree[$child] =& $flat[$child]; } } return $tree; } // Recursion function function treeByRecursion($flatTree, $root = null) { $return = []; foreach($flatTree as $child => $parent) { if ($parent == $root) { unset($flatTree[$child]); $return[$child] = treeByRecursion($flatTree, $child); } } return $return ?: []; } // Benchmark reference $t1 = microtime(true); $tree = treeByReference($flatTree); echo 'Reference: ', (microtime(true) - $t1), PHP_EOL; // Benchmark recursion $t2 = microtime(true); $tree = treeByRecursion($flatTree); echo 'Recursion: ', (microtime(true) - $t2), PHP_EOL; 

产出本身就说明了这一点：

 Array count: 255493 Reference: 0.3259289264679 (less than 0.4s) Recursion: 6604.9865279198 (almost 2h) 

Answer 6

以下是我想到的：

 $arr = array( 'H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null ); $nested = parentChild($arr); print_r($nested); function parentChild(&$arr, $parent = false) { if( !$parent) { //initial call $rootKey = array_search( null, $arr); return array($rootKey => parentChild($arr, $rootKey)); }else { // recursing through $keys = array_keys($arr, $parent); $piece = array(); if($keys) { // found children, so handle them if( !is_array($keys) ) { // only one child $piece = parentChild($arr, $keys); }else{ // multiple children foreach( $keys as $key ){ $piece[$key] = parentChild($arr, $key); } } }else { return $parent; //return the main tag (no kids) } return $piece; // return the array built via recursion } } 

输出：

 Array ( [D] => Array ( [G] => Array ( [H] => H [F] => F ) [E] => Array ( [A] => A [C] => Array ( [B] => B ) ) ) ) 

Answer 7

那么，为了parsingUL和LI，就是这样的：

 $array = array ( 'H' => 'G' 'F' => 'G' 'G' => 'D' 'E' => 'D' 'A' => 'E' 'B' => 'C' 'C' => 'E' 'D' => 'NULL' ); recurse_uls ($array, 'NULL'); function recurse_uls ($array, $parent) { echo '<ul>'; foreach ($array as $c => $p) { if ($p != $parent) continue; echo '<li>'.$c.'</li>'; recurse_uls ($array, $c); } echo '</ul>'; } 

但我很想看到一个解决scheme，不需要你频繁地遍历数组…

Answer 8

如何创builddynamic树视图和菜单

第1步：首先我们将在mysql数据库中创buildtreeview表。 此表包含四个column.id是任务ID，name是任务名称。

 - -- Table structure for table `treeview_items` -- CREATE TABLE IF NOT EXISTS `treeview_items` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(200) NOT NULL, `title` varchar(200) NOT NULL, `parent_id` varchar(11) NOT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=7 ; -- -- Dumping data for table `treeview_items` -- INSERT INTO `treeview_items` (`id`, `name`, `title`, `parent_id`) VALUES (1, 'task1', 'task1title', '2'), (2, 'task2', 'task2title', '0'), (3, 'task3', 'task1title3', '0'), (4, 'task4', 'task2title4', '3'), (5, 'task4', 'task1title4', '3'), (6, 'task5', 'task2title5', '5'); 

第2步：树视图recursion方法我创build了下面的树createTreeView（）方法，如果当前任务ID大于prev任务ID调用recursion。

 function createTreeView($array, $currentParent, $currLevel = 0, $prevLevel = -1) { foreach ($array as $categoryId => $category) { if ($currentParent == $category['parent_id']) { if ($currLevel > $prevLevel) echo " <ol class='tree'> "; if ($currLevel == $prevLevel) echo " </li> "; echo '<li> <label for="subfolder2">'.$category['name'].'</label> <input type="checkbox" name="subfolder2"/>'; if ($currLevel > $prevLevel) { $prevLevel = $currLevel; } $currLevel++; createTreeView ($array, $categoryId, $currLevel, $prevLevel); $currLevel--; } } if ($currLevel == $prevLevel) echo " </li> </ol> "; } 

第3步：创build索引文件以显示树视图。 这是treeview示例的主要文件，在这里我们将调用具有所需参数的createTreeView（）方法。

  <body> <link rel="stylesheet" type="text/css" href="_styles.css" media="screen"> <?php mysql_connect('localhost', 'root'); mysql_select_db('test'); $qry="SELECT * FROM treeview_items"; $result=mysql_query($qry); $arrayCategories = array(); while($row = mysql_fetch_assoc($result)){ $arrayCategories[$row['id']] = array("parent_id" => $row['parent_id'], "name" => $row['name']); } ?> <div id="content" class="general-style1"> <?php if(mysql_num_rows($result)!=0) { ?> <?php createTreeView($arrayCategories, 0); ?> <?php } ?> </div> </body> 

第4步：创buildCSS文件style.css这里我们将写所有的CSS相关类，目前我正在使用顺序列表来创build树视图。 你也可以在这里改变图像path。

 img { border: none; } input, select, textarea, th, td { font-size: 1em; } /* CSS Tree menu styles */ ol.tree { padding: 0 0 0 30px; width: 300px; } li { position: relative; margin-left: -15px; list-style: none; } li.file { margin-left: -1px !important; } li.file a { background: url(document.png) 0 0 no-repeat; color: #fff; padding-left: 21px; text-decoration: none; display: block; } li.file a[href *= '.pdf'] { background: url(document.png) 0 0 no-repeat; } li.file a[href *= '.html'] { background: url(document.png) 0 0 no-repeat; } li.file a[href $= '.css'] { background: url(document.png) 0 0 no-repeat; } li.file a[href $= '.js'] { background: url(document.png) 0 0 no-repeat; } li input { position: absolute; left: 0; margin-left: 0; opacity: 0; z-index: 2; cursor: pointer; height: 1em; width: 1em; top: 0; } li input + ol { background: url(toggle-small-expand.png) 40px 0 no-repeat; margin: -0.938em 0 0 -44px; /* 15px */ height: 1em; } li input + ol > li { display: none; margin-left: -14px !important; padding-left: 1px; } li label { background: url(folder-horizontal.png) 15px 1px no-repeat; cursor: pointer; display: block; padding-left: 37px; } li input:checked + ol { background: url(toggle-small.png) 40px 5px no-repeat; margin: -1.25em 0 0 -44px; /* 20px */ padding: 1.563em 0 0 80px; height: auto; } li input:checked + ol > li { display: block; margin: 0 0 0.125em; /* 2px */} li input:checked + ol > li:last-child { margin: 0 0 0.063em; /* 1px */ } 

更多细节