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

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”,没有隐含的命名结构,这只是为了让它更具可读性。

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


当前回答

如果元素是按树顺序排列的,如你的例子所示,你可以使用以下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访问节点。

其他回答

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

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

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

从Oracle 9i开始,您可以使用CONNECT BY。

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

从SQL Server 2005开始,您可以使用递归公共表表达式(CTE)。

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

两者都将输出以下结果。

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

考虑使用像neo4j这样的nosql工具来处理层次结构。 例如,像linkedin这样的网络应用程序使用couchbase(另一个nosql解决方案)

但是nosql只能用于数据集市级别的查询,而不能用于存储/维护事务

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

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