我正在使用下面的树结构并计划为下面开发一个数据库模式。
我到目前为止的发展如下，
我遇到的问题是，如果我搜索 Y，应该生成下面的树。
我使用的逻辑是，Y 有两个交叉引用 X、Z，这两个节点应该在图中，父节点一直到起始父节点。
鉴于我正在使用 PHP 使用 mysql db 表生成这棵树，如上所示。DB结构可以改变。我在谷歌上搜索了类似的树结构，但找不到任何帮助。
我不是要你为我写代码。我要问的只是一些指导方针，应该如何做到这一点。
我发现以下内容很有帮助，但与我的情况仍然不同
如果有人可以请告诉我应该使用哪些 php 库来生成树以及要使用的合适的数据库结构是什么？
让我重申这个问题，以确保我理解正确。你有节点和两种关系——箭头和垂直线。然后给定一个节点 N，您想要生成具有以下递归规则的节点子集 S(N)：
集合 S(N) 是满足这些规则的最小节点集合。
您给出的 N 为 Y 的示例似乎证实了这些规则。
但是，还有另一组不同但（至少对我而言）更自然的规则集，上面的规则 1 被替换为
在续集中，我将假设规则 0,1,2 已由您的示例确认，但类似的方法可用于规则 0,1',2 或任何修改。
此外，我了解您的第 7 行表格中存在错误，应该是：
7 B2 B B1,B3 (not B2,B3)
现在到建议的解决方案。
我将首先稍微修改您的表结构：由于“id”是您的主键，因此外键的规则是指向相关条目的主键。也就是说，在你的情况下，我会用“node_name”或类似的东西替换“node_id”，以免与“id”混淆，并用它们的“id”替换“node_parent_id”和“cross_ref”的条目。例如，第 15 行看起来像这样：
15 'Y' [13] [14,16]
或者，如果您出于可读性原因更喜欢，您可以使用 A、B、X、Y 等作为主键，只要它们是唯一的，当然，那么您的表将保持不变，除了“id”字段不需要。我将假设第一种情况，但您可以通过简单的替换使其适应第二种情况。
就桌子而言，这就是您所需要的。
现在你需要一个递归函数来为每个给定的节点 N 生成子图 S(N)。
我将集合 S 实现为其节点的所有 'id' 的数组 $set。然后我将定义两个函数 - 一个最初基于规则 1,2 扩展集合，另一个仅基于规则 2 扩展集合。
为简单起见，我将假设您的表作为关联数组 $rows of rows 导入内存，这样 $rows[$id] 将 'id' 等于 $id 的行再次表示为关联数组。所以
$rows[15] = array('id'=>15,
'node_name'=>'Y',
'node_parent_id'=>array(13),
'cross_ref'=>array(14,16)
);
这是函数的代码：
function initial_expand_set ($node_id) {
global($rows); // to access the array from outside
$set = array($node_id); // Rule 0
$row = $rows[$node_id]; // Get current Node
$parents = $row['node_parent_id']; // Get parents of the Node
$set = $parents ? array_merge ($set, $parents) : $set; // Join parents to the set
$vert_brothers = $row['cross_ref']; // Get vertical relations
$set = $vert_brothers ? array_merge ($set, $vert_brothers) : $set;
$set = expand_set($set); // Recursive function defined below
return $set;
}
和递归函数：
// iterate over nodes inside the set, expand each node, and merge all together
function expand_set (array $set) {
global($rows);
$expansion = $set; // Initially $expansion is the same as $set
foreach ($set as $node_id) {
$row = $rows[$node_id]; // Get Node
// Get the set of parents of the Node - this is our new set
$parents = $row['node_parent_id']; // Get parents of the Node
// apply the recursion
$parents_expanded = expand_set($parents);
// merge with previous expansion
$expansion = array_merge($expansion, $parents_expanded);
}
// after the loop is finished getting rid of redundant entries
// array_unique generates associative array, for which I only collect values
$expansion = array_values( array_unique($expansion) );
return $expansion;
}
希望对你有效。:)
如果需要任何进一步的细节或解释，我将很乐意提供帮助。
PS。对于读者中的学究，请注意我在 '(' 之前使用空格来定义函数，而没有空格用于函数调用，正如 Douglas Crokford 所推荐的那样。
您的数据库结构似乎不是一棵树，它只是图表。
我建议你放弃这种结构的关系数据库，看看像Neo4j、OrientDB和Infinite Graph这样的图形数据库。
但是如果你被迫使用 MySQL，你可以使用FlockDB，它可以用来遍历 MySQL 节点（将行视为节点），但有一些限制。或者您可以测试另一个 MySQL 引擎，如OQGRAPH，它为 MySQL 和 MariaDB 提供图形引擎。
node_parent_id您的数据库结构未标准化，因为您在和中都有多个 id cross_refer。您应该将此信息分开到单独的表中。
因此，您将拥有自己的nodes表格，以及用于描述父子关系的第二个表格；该表将有一个子节点 ID 和一个父节点 ID。
交叉引用应该在第三个表中，它同样有两个节点 id 列，但是有两种方法可以做到这一点，因为交叉引用是双向的。一种方法是每个交叉引用只存储一次，这意味着当您查询表时，您必须检查两种可能性（X 和 Y 之间的交叉引用可以存储在第一列中的 X 和第二列中的 Y，或相反，所以要找到 X 你必须检查两列）。另一种方法是将每个交叉引用存储两次，每个方向一次。这使得查询更简单，但它存储了冗余数据并可能导致不一致，例如，如果由于某种原因删除了一个引用而另一个没有删除。
使用这种结构查找路径变得更加简单，因为您不必额外解析逗号分隔的字符串，这既复杂又低效。
您还可以使用它来确保引用完整性，例如，一个节点没有在数据库中实际不存在的父 id。
有关更多信息，请研究“数据库规范化”。（或者如果你愿意的话，你可以用“z”来拼写它；-P）
我发现的唯一一个用于处理图形的 PHP 库是 PEAR“Structures_Graph”包（http://pear.php.net/manual/en/package.structures.structures-graph.php）。它目前没有得到维护，重要的功能（例如删除节点）没有实现，并且存在严重的错误（例如无法在 Windows 7 下安装）。它看起来不像那个包，以其目前的形式，将是有用的。
操作图所需的基本操作可以分为更改图（变异）和查询图（非变异）的操作。
示例：要手动构建具有以“B”开头的节点名称的图形部分，代码将是：
$nodeID_B = CreateNode(“B”);
$nodeID_B1 = CreateNode(“B1”);
$nodeID_B2 = CreateNode(“B2”);
$nodeID_B3 = CreateNode(“B3”);
CreateHorizontalEdge($nodeID_B, $nodeID_B1);
CreateHorizontalEdge($nodeID_B, $nodeID_B2);
CreateHorizontalEdge($nodeID_B, $nodeID_B3);
CreateVerticalEdge($nodeID_B1, $nodeID_B2);
CreateVerticalEdge($nodeID_B2, $nodeID_B3);
手动删除名称为“B3”的节点的代码：
// Must remove all edges that connect to node first
DeleteVerticalEdge($nodeID_B2, $nodeID_B3);
DeleteHorizontalEdge($nodeID_B, $nodeID_B3);
// Now no edges connect to the node, so it can be safely deleted
DeleteNode($nodeID_B3);
示例：要获取要包含在问题中描述的子树中的节点列表，请结合 GetHorizontalAncestorNodes($nodeID) 和 GetVerticalSiblingNodes($nodeID) 的结果。
您将始终需要一个“节点”表来保存 nodeID 和 nodeName。该表可以扩展以保存与节点相关的其他信息。
由于垂直边不具有传递性，因此可以简单地将有关它们的信息放在“VerticalEdges”表中，其中列有 vEdgeID、firstNodeID、secondNodeID。
如何存储水平边缘信息有多种选择。一方面，数据结构和变异操作可以很简单，但代价是使某些查询操作更慢、更复杂。另一方面，数据结构可能稍微复杂一些，但可能更大（在最坏的情况下随着节点数量呈指数增长），具有更复杂的变异操作，但查询更简单、更快。决定哪种实现最适合您将取决于图表的大小以及与查询它们的次数相比它们的更改频率。
我将描述三种可能的数据结构来表示图，从简单到复杂。我将仅针对最后一组数据结构详细介绍上面列出的操作的算法。我认为这组结构最适合查询与更改比例较高的较小图。
请注意，所有数据结构都有我上面讨论过的“Nodes”和“VerticalEdges”表。
第一个数据结构有一个“HorizontalEdges”表，其中包含 hEdgeID、sourceNodeID 和 destinationNodeID 列。变异函数很简单，大部分代码都是抛出异常的错误检查代码。非变异函数 HorizontalConnectionExists、GetHorizontalAncestorNodes 和 GetHorizontalDescendentNodes 将很复杂并且可能很慢。每次调用它们都会递归遍历HorizontalEdges 表并收集nodeID。这些集合直接返回给后面的两个函数，而 HorizontalConnectionExists 可以终止并在搜索起始节点的后代时找到结束节点并返回 true。如果搜索完成但没有找到结束节点，它将返回 false。
第二个数据结构也有一个与上述相同的 HorizontalEdges 表，但也有第二个表“HorizontalTransitiveClosures”，列 hTCID、startNodeID 和 endNodeID。对于每对开始节点和结束节点，该表中有一行，以便可以从开始节点到结束节点跟踪使用水平边的路径。
示例：对于问题中的图表，此表中包含节点 A 的行（为了简化符号，我将使用名称，而不是整数节点 ID 来标识节点，并省略 hTCID 列）是：
A, A2
A, A2B1
A, A2B1B2
A, X
A, Y
A, Z
包含节点 A2B1 的行（第一个也在上面的集合中）是：
A, A2B1
A2, A2B1
B, A2B1
B1, A2B1
A2B1, A2B1B2
A2B1, X
A2B1, Y
A2B1, Z
在更糟糕的情况下，此表按节点数的平方进行缩放。
使用此数据结构，HorizontalConnectionExists、GetHorizontalAncestorNodes 和 GetHorizontalDescendentNodes 可以实现为对 HorizontalTransitiveClosures 表的简单搜索。复杂性移至 CreateHorizontalEdge 和 DeleteHorizontalEdge 函数。DeleteHorizontalEdge 特别复杂，需要对算法的工作原理进行一些解释。
我将讨论的最终数据结构将水平边缘信息存储在两个表中。第一个，“HorizontalTransitiveClosurePaths”有列 hTCPathID、startNodeID、endNodeID、pathLength。第二个表“PathLinks”具有列 PathLinkID、hTCPathID、sourceNodeID、destinationNodeID。
HorizontalTransitiveClosurePaths 表与上述数据结构中的 HorizontalTransitiveClosures 表类似，但它对于可以实现传递闭包的每个可能路径都有一行，而不是每个传递闭包一行。例如，在问题所示的图表中，HorizontalTransitiveClosures 表将有一行 (B, A2B1B2) （如上的简写符号）用于从 B 开始并结束 A2B1B2 的闭包。HorizontalTransitiveClosurePaths 表将有两行：(10, B, A2B1B2, 3) 和 (11, B, A2B1B2, 2)，因为从 B 到 A2B1B2 有两种方法。PathLinks 表描述了这些路径中的每一个，每个边都有一行组成路径。对于从 B 到 A2B1B2 的两条路径，行是：
101, 10, B, B1
102, 10, B1, A2B1
103, 10, A2B1, A2B1B2
104, 11, B, B2
105, 11, B2, A2B1B2
不需要 HorizonalEdges 表，因为可以通过选择 HorizontalTransitiveClosurePaths 表中长度为 1 的行来找到边。
查询函数的实现方式与上述传递闭包数据结构相同。由于闭包可能存在多个路径，因此需要使用 GROUP BY 运算符。例如，返回 ID 为 :nodeid 的节点的祖先的所有节点的 SQL 查询是： SELECT startNodeID from HorizontalTransitiveClosurePaths WHERE endNodeID = :nodeid GROUP BY startNodeID
要实现 DeleteHorizontalEdge，请在 PathLinks 中搜索包含边缘的所有路径的 hTCPathID。然后从 HorizontalTransitiveClosurePaths 表中删除这些路径以及与 PathLinks 表中的路径关联的所有边。
要实现 CreateHorizontalEdge($souceNodeID, $destinationNodeID)，首先在 HorizontalTransitiveClosurePaths 表中搜索以 $souceNodeID 结尾的路径——这是“祖先路径集”。在 HorizontalTransitiveClosurePaths 中搜索从destinationNodeID 开始的路径——这是“下降路径集”。现在将来自以下 4 个组的新路径（其中一些可能为空）插入到 HorizontalTransitiveClosurePaths 表中，并将这些路径的链接插入到 PathLinks 表中。
示例：一个图由 6 个节点组成：A1、A2、B、C、D1 和 D2。它有 4 个边，(A1, B), (A2, B), (C, D1), (C, D2)。HorizontalTransitiveClosurePaths 表（使用节点名称而不是数字）是：
1, A1, B, 1
2, A2, B, 1
3, C, D1, 1
4, C, D2, 1
PathLinks 表是：
1, 1, A1, B
2, 2, A2, B
3, 3, C, D1
4, 4, C, D2
现在我们添加从 B 到 C 的边。祖先路径集是 (1, 2)，后代路径集是 (3, 4) 4 组中添加的路径分别是：
水平传递闭包路径：
6、A1、C、2
7、A2、C、2
路径链接：
6、6、A1、B
7、6、B、C
8、7、A2、B
9、7、B、C
水平传递闭包路径：
8、B、D1、2
9、B、D2、2
路径链接：
10、8、B、C
11、8、C、D1
12、9、B、C
13、9、C、D2
水平传递闭包路径：
10、A1、D1、3
11、A1、D2、3
12、A2、D1、3
13、A2、D2、3
路径链接：
14、10、A1、B
15、10、B、C
16、10、C、D1
17、11、A1、B
18、11、B、C
19、11、C、D2
20、12、A2、B
21、12、B、C
22、12、C、D1
23, 13, A2, B
24、13、B、C
25、13、C、D2
让我知道答案的任何部分是否需要进一步澄清。
如果我理解正确，你有一个经典的多对多自引用逻辑表结构。这可以通过创建三个表轻松处理：一个代表您的“节点”，另一个代表节点之间的父子“关联”，另一个代表兄弟关系。我不相信您需要直接表示兄弟关系，因为这些可以从父子关系中推断出来。但是，由于您没有为所有兄弟姐妹呈现“绿色”关系线，我假设这是一个“特殊”关系。表格/列可以建模如下：
节点
节点映射
node_sibling_map
为了填充您在此模型中描述的表，您需要发出以下命令。（省略引号）。
这是一个相当复杂的问题，您正在处理的问题。可能值得检查以下文章：
http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o http://www.freepatentsonline.com/6633886.html