假设你有一个扁平的表,存储一个有序的树层次结构:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

这是一个图表,我们有[id] Name。根节点0是虚构的。

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

您将使用什么极简的方法将其输出到HTML(或文本,就此而言),作为一个正确有序、正确缩进的树?

进一步假设您只有基本的数据结构(数组和hashmap),没有带有父/子引用的花哨对象,没有ORM,没有框架,只有您的两只手。该表表示为一个结果集,可以随机访问。

伪代码或简单的英语是可以的,这纯粹是一个概念问题。

附加问题:在RDBMS中是否存在从根本上更好的方法来存储这样的树结构?


编辑和添加

回答一位评论者(Mark Bessey)的问题:根节点是不必要的,因为无论如何它都不会显示。ParentId = 0是表示“这些是顶级”的惯例。Order列定义了具有相同父节点的节点如何排序。

我所说的“结果集”可以被描绘成一个hashmap数组(继续使用这个术语)。因为我的例子本来就应该在那里。有些答案是额外的,首先构建它,但这没关系。

树可以任意深。每个节点可以有N个子节点。不过,我脑子里并没有“数百万条”树。

不要把我选择的节点命名(“节点1.1.1”)误认为是可以依赖的。节点也可以被称为“Frank”或“Bob”,没有隐含的命名结构,这只是为了让它更具可读性。

我已经发布了我自己的解决方案,所以你们可以把它拆成碎片。


当前回答

如果有选择的话,我会用对象。我将为每条记录创建一个对象,其中每个对象都有一个子集合,并将它们全部存储在一个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密集的。这是令人讨厌的。如果可以选择的话,选择面向对象的方法。

其他回答

这写得很快,既不漂亮也不高效(加上它自动装箱很多,在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;
    }
}

这是一个相当老的问题,但由于有很多观点,我认为有必要提出一个替代方案,在我看来,非常优雅的解决方案。

为了读取树结构,可以使用递归通用表表达式(CTEs)。它提供了一次获取整个树结构的可能性,有关于节点的级别,它的父节点和父节点的子节点顺序的信息。

让我向你展示这在PostgreSQL 9.1中是如何工作的。

Create a structure CREATE TABLE tree ( id int NOT NULL, name varchar(32) NOT NULL, parent_id int NULL, node_order int NOT NULL, CONSTRAINT tree_pk PRIMARY KEY (id), CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) REFERENCES tree (id) NOT DEFERRABLE ); insert into tree values (0, 'ROOT', NULL, 0), (1, 'Node 1', 0, 10), (2, 'Node 1.1', 1, 10), (3, 'Node 2', 0, 20), (4, 'Node 1.1.1', 2, 10), (5, 'Node 2.1', 3, 10), (6, 'Node 1.2', 1, 20); Write a query WITH RECURSIVE tree_search (id, name, level, parent_id, node_order) AS ( SELECT id, name, 0, parent_id, 1 FROM tree WHERE parent_id is NULL UNION ALL SELECT t.id, t.name, ts.level + 1, ts.id, t.node_order FROM tree t, tree_search ts WHERE t.parent_id = ts.id ) SELECT * FROM tree_search WHERE level > 0 ORDER BY level, parent_id, node_order;

以下是调查结果:

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)

树节点按深度排序。在最终输出中,我们将在随后的行中显示它们。

对于每一层,它们都是根据父级中的parent_id和node_order进行排序的。这告诉我们如何在输出链接节点中将它们按此顺序呈现给父节点。

有了这样的结构,用HTML制作一个真正漂亮的演示就不难了。

递归cte可用于PostgreSQL, IBM DB2, MS SQL Server, Oracle和SQLite。

如果你想阅读更多关于递归SQL查询的内容,你可以查看你最喜欢的DBMS的文档,或者阅读我关于这个主题的两篇文章:

做它在SQL:递归树遍历 了解SQL递归查询的强大功能

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

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

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

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

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

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

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

如果您使用嵌套集(有时称为Modified preorder Tree Traversal),您可以通过一个查询以树顺序提取整个树结构或其中的任何子树,但插入的代价更大,因为您需要管理通过树结构描述有序路径的列。

对于django-mptt,我使用了这样的结构:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

它描述了一个像这样的树(id代表每一项):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

或者,作为一个嵌套的集合图,这使得left和right值的工作方式更加明显:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

如您所见,要获得给定节点的整个子树,按照树的顺序,您只需选择在其left和right值之间具有left和right值的所有行。检索给定节点的祖先树也很简单。

The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.

为了实际使用这些数据来显示树,我创建了一个tree_item_iterator实用函数,对于每个节点,它应该为您提供足够的信息来生成您想要的任何类型的显示。

更多关于MPTT的信息:

SQL中的树 在数据库中存储分层数据 在MySQL中管理分层数据