我有一个Web系统，其中有一个经典的父子菜单保存在数据库中，字段id为PK，parent_id指向拥有的菜单。 (是的，我知道这不能很好地扩展，但这是另一个主题)。

因此，对于这些记录(id-parent_id对)：

0-7 0-4 4-9 4-14 4-16 9-6

我有这棵树：

0
├ 7
└ 4
  ├ 9
  | └ 6     
  ├ 14
  └ 16

我需要隐藏一个顶部节点，因此我必须列出该节点的所有子节点，即对于4，它们将是(9、6、14、16)。顺序无关紧要。

我很困惑...这是否适合经典的树木问题？还是一个图？

如何使用php构成此结构并解决此问题？

解决方案

回答

这是使用递归的绝佳机会！

伪代码：

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

编辑：没注意到树是相邻列表格式。在开始使用它之前，我可能会将其构建到实际的树数据结构中。只需遍历所有对(在我们第一次看到它们时创建节点)并链接它们即可。我认为应该很容易...

回答

相邻列表模型很难处理。我现在所在的公司将它们用于层次结构，这会造成很大的麻烦。我已经为先前的雇主成功地使用了Celko的嵌套集模型，它们对于创建，维护和使用层次结构(树)非常有用。

我找到了描述他们的链接：http://www.intelligententerprise.com/001020/celko.jhtml

但是，我还建议由Joe Celko撰写的书" SQL for Smarties：高级SQL编程"，其中涉及嵌套集。

Joe Celko的《 Smarties SQL：高级SQL编程》

聪明人的SQL中的Joe Celko的树和层次结构

回答

这是一个图形问题。查看BFS(深度优先搜索)和DFS(深度优先搜索)。

回答

对于嵌套集实现，这是微不足道的。请参阅此处以获取更多详细信息：

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

否则，编写如下内容：

def get_subtree(node)
  if children.size > 0
    return children.collect { |n| get_subtree(n) }
  else
    return node
  end
end