如果可以创建嵌套的哈希映射或数组，那么我只需从表的开头往下走，并将每个项添加到嵌套数组中。我必须跟踪每一行到根节点，以便知道要插入到嵌套数组中的哪一层。我可以使用记忆，这样我就不需要一遍又一遍地查找相同的父节点。

编辑:我会先将整个表读入一个数组，这样它就不会重复查询DB。当然，如果您的表非常大，这是不实际的。

在构建结构之后，我必须先对其进行深度遍历，并打印出HTML。

没有更好的基本方法来存储这些信息使用一个表(我可能是错的;)，并希望看到一个更好的解决方案)。然而，如果您创建了一个使用动态创建的db表的方案，那么您以牺牲简单性和SQL地狱的风险为代价打开了一个全新的世界;)。

如果有选择的话，我会用对象。我将为每条记录创建一个对象，其中每个对象都有一个子集合，并将它们全部存储在一个assoc数组(/hashtable)中，其中Id是键。并在集合中闪动一次，将子元素添加到相关的子字段中。简单。

但是因为你限制一些好的OOP的使用是没有乐趣的，我可能会基于:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

编辑:这与其他几个条目类似，但我认为它稍微干净一些。我要补充一点:这是非常sql密集的。这是令人讨厌的。如果可以选择的话，选择面向对象的方法。

要扩展Bill的SQL解决方案，基本上可以使用平面数组来实现相同的功能。此外，如果你的字符串都有相同的长度，你的最大子代数是已知的(比如在一个二叉树中)，你可以使用一个单一的字符串(字符数组)。如果你有任意数量的孩子，事情就会变得复杂一些……我必须检查我的旧笔记，看看能做些什么。

然后，牺牲一点内存，特别是如果你的树是稀疏的和/或不平衡的，你可以，通过一些索引数学，通过存储你的树随机访问所有的字符串，宽度优先在数组中，就像这样(对于二叉树):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

你知道弦的长度，你知道 我现在在工作，所以不能花太多时间在上面，但有兴趣，我可以获取一些代码来做到这一点。 我们过去用它来搜索由DNA密码子组成的二叉树，一个构建树的过程，然后我们将其平铺以搜索文本模式，当找到时，尽管索引数学(从上面反向)，我们将节点找回…非常快速和有效，我们的树很少有空节点，但我们可以在一瞬间搜索千兆字节的数据。

有一些很好的解决方案利用了sql索引的内部btree表示。这是基于1998年左右的一些伟大的研究。

下面是一个示例表(在mysql中)。

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

树表示中唯一需要的字段是:

tw:从左到右的DFS预购索引，其中根= 1。 pa:对父节点的引用(使用tw)，根节点为空。 sz:包括节点本身在内的节点分支的大小。 Nc:用作语法糖。它是tw+sz，表示节点的“下一个子”的tw。

下面是一个例子，24个节点填充，按tw排序:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

每个树的结果都是非递归的。 例如，要获取tw='22'节点的父节点列表

的祖先

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

兄弟姐妹和孩子是微不足道的-只需使用pa字段按tw排序。

的后代

例如，根在tw = 17的节点的集合(分支)。

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

额外的笔记

当读取的数量远远大于插入或更新的数量时，这种方法非常有用。

因为树中节点的插入、移动或更新需要调整树，所以在开始操作之前必须锁定表。

插入/删除成本很高，因为tw索引和sz(分支大小)值需要在插入点之后的所有节点上更新，并且需要分别对所有祖先节点更新。

分支移动涉及到将分支的tw值移出范围，因此在移动分支时禁用外键约束也是必要的。移动一个分支需要四个查询:

把树枝移出范围。 填补它留下的缺口。(剩下的树现在是正常化的)。 打开它要去的地方的缺口。 移动树枝到它的新位置。

调整树查询

树中间隙的打开/关闭是创建/更新/删除方法使用的一个重要子函数，因此我将它包含在这里。

我们需要两个参数——一个标志表示是缩小还是扩大，另一个是节点的tw索引。因此，例如tw=18(分支大小为5)。让我们假设我们正在缩小(删除tw) -这意味着我们在下面的例子的更新中使用'-'而不是'+'。

我们首先使用一个(稍微改变的)祖先函数来更新sz值。

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

然后我们需要为那些tw高于要移除的分支调整tw。

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

然后我们需要调整那些pa的tw比要移除的分支高的父类。

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

比尔的回答非常好，这个答案增加了一些东西，这让我希望SO支持线程的答案。

无论如何，我想要支持树结构和Order属性。我在每个Node中都包含了一个名为leftSibling的属性，它所做的事情与Order在原始问题中所做的事情相同(保持从左到右的顺序)。

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

更多细节和SQL代码在我的博客。

谢谢你，比尔，你的回答对我的开始很有帮助!

如果可以创建嵌套的哈希映射或数组，那么我只需从表的开头往下走，并将每个项添加到嵌套数组中。我必须跟踪每一行到根节点，以便知道要插入到嵌套数组中的哪一层。我可以使用记忆，这样我就不需要一遍又一遍地查找相同的父节点。

编辑:我会先将整个表读入一个数组，这样它就不会重复查询DB。当然，如果您的表非常大，这是不实际的。

在构建结构之后，我必须先对其进行深度遍历，并打印出HTML。

没有更好的基本方法来存储这些信息使用一个表(我可能是错的;)，并希望看到一个更好的解决方案)。然而，如果您创建了一个使用动态创建的db表的方案，那么您以牺牲简单性和SQL地狱的风险为代价打开了一个全新的世界;)。