检索的所有节点在一棵树是儿童的另外一个

Question

我有一个网络系统，该系统具有一个经典的父母-孩子的菜单保存在一个数据库，用领域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?

Answer 1

这是一个完美的机会，使用递归!

伪码：

nodeList = {}
enumerateNodes(rootNode, nodeList);

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

编辑：没有注意到你的树是在相邻的列表格式。我可能只是建成一个实际的树datastructure我开始之前与它的工作。只是循环，通过所有对(建立节点你第一次看到他们)和联他们。我 想想 它应该是很容易的...

Answer 2

相邻清单模型是非常难以处理的。公司，我现在使用它们的层次结构，它会导致极大的麻烦。我已经成功地使用Celko的嵌套模型的现有雇主和他们的工作很大的创建、维护和使用层次结构的(树)。

我发现这个的链接，其中描述了他们： http://www.intelligententerprise.com/001020/celko.jhtml

但我还推荐这本书"SQL为利己:高级SQL编写的"乔Celko和涵盖嵌套套。

乔Celko的SQL为利己:高级SQL编程

乔Celko的树木和层次结构中SQL为利己

Answer 3

这是一个曲线图问题。检查了 BFS(广度第一次搜索) 和 DFS(深度的第一个搜索)。.你可以google出来的那些条款和找到数以百计的实现在网络上。

Answer 4

这是微不足道有一个嵌套的执行。在这里看到更多的详细信息：

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