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

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

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

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

如果元素是按树顺序排列的，如你的例子所示，你可以使用以下Python示例:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

这样做的目的是维护一个表示树中当前位置的堆栈。对于表中的每个元素，它弹出堆栈元素(关闭匹配的div)，直到找到当前项的父元素。然后它输出该节点的开始并将其推入堆栈。

如果希望使用缩进而不是嵌套元素输出树，可以简单地跳过print语句来打印div，并在每个项之前打印等于堆栈大小的若干倍的空格。例如，在Python中:

print "  " * len(stack)

您还可以轻松地使用此方法构造一组嵌套的列表或字典。

编辑:我从你的澄清中看到，这些名称并不是节点路径。这就提出了另一种方法:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

这将构造一个元组数组树(!)。Idx[0]表示树的根。数组中的每个元素都是一个二元组，由节点本身及其所有子元素的列表组成。构造后，可以保留idx[0]并丢弃idx，除非您希望通过节点的ID访问节点。

这写得很快，既不漂亮也不高效(加上它自动装箱很多，在int和Integer之间转换很烦人!)，但它是有效的。

这可能打破了规则，因为我创建自己的对象，但嘿，我这样做是为了从实际工作中转移注意力:)

这还假定在开始构建Nodes之前，resultSet/table已完全读入某种结构，如果您有数十万行，这不是最佳解决方案。

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

您可以使用hashmap模拟任何其他数据结构，因此这并不是一个可怕的限制。从上到下扫描，为数据库的每一行创建hashmap，为每一列创建一个条目。将这些hashmap添加到“master”hashmap中，并以id为键。如果任何节点都有一个尚未见过的“父”节点，请在主hashmap中为它创建一个占位符条目，并在看到实际节点时填充它。

要将其打印出来，只需对数据进行简单的深度优先遍历，并在此过程中跟踪缩进级别。您可以通过为每一行保留一个“子”条目，并在扫描数据时填充它来简化这一点。

至于是否有“更好”的方法在数据库中存储树，这取决于您将如何使用数据。我曾经见过一些系统，它们具有已知的最大深度，但却为层次结构中的每个级别使用不同的表。如果树中的级别并不完全相同(顶级类别与叶类别不同)，那么这就很有意义了。

假设你知道根元素是0，下面是输出到文本的伪代码:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

有一些很好的解决方案利用了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;