algorithm - 什么才是最有效率的/ 简洁的方法来解析平面表转换成一个树?

  显示原文与译文双语对照的内容

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


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 ( 或者文字,比如) 输出为正确有序的缩进树?

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

伪代码或者纯英语没关系,这纯粹是一个概念问题。

额外的问题:在RDBMS中有一个基本更好的方法来存储树形结构?


编辑和添加

回答一个( 注释符标记 Bessey'问题: 根本不需要根节点,因为它永远不会被显示。 ParentId = 0表示表示"这些是顶层"的约定。 顺序column列定义了具有相同父级的节点如何排序。

我所说的"结果集"是一个 hashmaps ( 留在那个术语中) 数组。 我的例子应该已经存在了。 一些答案是额外的英里,首先构造它,但这可以。

树可以任意的深。 每个节点可以有N 个子节点。 我还没有意识到"数以百万计的条目"树。

不要误解我选择的节点命名('节点 1.1.1') 为依赖于。 这些节点也可以被称为'frank'或者'bob',没有命名结构,这只是让它可读。

我已经发布了自己的解决方案,这样你们就可以把它拉到一起了。

时间:

如果你使用嵌套集( 有时被称为修改的Pre-order树遍历) 你可以提取整个树状结构或者任何子树( 例如在用树的顺序与单个查询,请在插入中昂贵的成本,如你需要管理列用于描述一个in-order路径通过付出三树结构。

对于 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

或者,作为一个嵌套集图表,它使得 lftrght 值的工作方式更加明显:

 __________________________________________________________________________
| 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
| |________________________________| |________________________________| |
|__________________________________________________________________________|

如你所见,来获得整个子树的树顺序,你只须中给定节点,选择所有行,对于具有 lft 和它的lft 之间和 rghtrght 值值。 检索给定节点的祖先树也很简单。

为了创建或者关闭 denormalisation gaps, level 列有点的,为方便起见,并且允许你重新启动 lftrghttree_id 列编号为每个top-level节点内容相比,这减少了列的数量受插入,移动和删除这些操作单轴晶体时,随着 lftrght 列必须进行相应的调整 在我试图围绕每个操作所需的查询时,我做了一些开发笔记

在实际使用这些数据来显示树的方面,我创建了一个 tree_item_iterator 实用程序函数,它为每个节点提供了足够的信息来生成任何你想要的显示类型。

关于MPTT的更多信息:

在 Oracle 9中,你可以使用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'

如果选择的话,我将使用对象。 我将为每个记录创建一个对象,其中每个记录都有一个 children 集合,并将它们存储在一个关联数组(/hashtable ) 中,该数组是。 然后一次通过集合,将孩子添加到相关的子字段。

,而是因为你被没有通过限制使用一些个良好的面向对象编程的娱乐上,我将很可能迭代 based:


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-intensive 。 它是令人讨厌 。如果进行选择的话,你可以进入面向对象的路线。

在我看来很优雅,它只是个满老问题 solution, 、但是就像上面有很多观点我认为值得来介绍另一种和。

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

让我向你展示一下如何在 PostgreSQL 9.1中工作。

  1. 创建结构

    
    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);
    
    
  2. 编写查询

    
    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中制作一个真正漂亮的演示就不难了。

    递归CTEs是 PostgreSQL,IBM DB2,MS SQL Server 和甲骨文中可用。

    如果你想更多地阅读递归SQL查询,你可以查看你最喜欢的DBMS的文档,或者阅读我的两篇文章,其中包括:

比尔的回答很不错,这个答案给了我一些东西,让我对它有了很好的支持。

无论如何,我想支持树结构和顺序属性。 我在每个节点中都包含了一个名为 leftSibling的属性,它做同样的事情 Order 是在原始问题( 维护left-to-right顺序) 中做的。

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代码。

感谢你的回答,你的回答有助于入门 !

这是快速编写的,既不是漂亮的( 再加上 autoboxes,在 intInteger 之间转换很烦人) 也不是高效的,但它可以工作。

可能在实际工作:),它即便不符合规则因为我要创建我自己的对象,但是嘿我解释这个作为导流

这还假定该结果集/表被完全读入某种形式的结构,它也不是最好的解决方案,然后再开始构建节点如果有几十万行。


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;
 }
}

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


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)

...