我正在构建Xamarin.Forms应用程序。我在SQLite数据库中有一个表,该表以树形保存分层数据。我们称之为TreeNode:
public class TreeNode
{
[PrimaryKey]
public int Id { get; set; }
[Indexed]
public int? ParentId {get; set;}
public string ParentPath { get; set; }
[Indexed]
public int Sort { get; set; }
public string Data { get; set; }
}
此树结构包含一个巨大的菜单(+ 100K节点)。树中的兄弟姐妹具有Sort
值来设置顺序。此属性的用途是:
让我们关注点2。考虑到Sort
属性,我想选择第一个分支直到第一个叶子。
作为示例,让我们看一下代表菜单的树(从here中提取):
1,0
|
------------------------------------------------------------------
2,1 93,2 4,3 5,4
| | | |
------------------------ ---------------------- ---------------- ----------
6,5 7,6 8,7 9,8 10,9 11,3 12,5 13,7 14,9 15,1 16,5 17,9 18,2 19,8
| | | |
---------- ---------- ---------- ----------
27,8 26,9 25,7 24,8 23,6 22,7 21,5 20,6
对于每个节点,第一个数字是Id
,第二个是对同一级别中每个同级的排序。因此,对于ID = 2的节点,Sort = 1,Id = 93的Sort = 2,依此类推。]
我研究了最近几天的递归查询,并且能够遍历树的顶部(宽度优先和深度优先),而且我知道如何获取给定节点的所有祖先。那里有很多例子。
正如我在第2点中所说,我想要的是一个递归查询,该查询将我的第一个分支返回到第一片叶子,或者将来还会出现其他情况,但让我坚持一下,我只希望第一个分支到达第一片叶子。在上面的示例中,我要从树中取回的节点是:
1,0 2,1 6,5
我尝试了类似的查询:
WITH RECURSIVE depth_first_traversal ( level, lineage, Id, ParentId, Sort, leaf ) AS ( SELECT CAST ( 1 AS INTEGER ) AS level, '00' || node.Sort AS lineage, node.Id AS Id, node.ParentId AS ParentId, node.Sort AS Sort, node.leaf AS leaf FROM node WHERE node.ParentId = 1 --Is NULL UNION ALL SELECT depth_first_traversal.level + 1, depth_first_traversal.lineage || '-' || '00' || node.sibling_number, node.node_id, node.parent_id, node.sibling_number, node.leaf FROM depth_first_traversal INNER JOIN node ON node.parent_id = depth_first_traversal.node_id --WHERE node.leaf = 1 I was trying to play with a leaf flag to reduce the CTE size ORDER BY lineage ) SELECT node_id, level, lineage, leaf FROM depth_first_traversal;
但是此查询返回我在初始选择中给定节点的所有分支。因此,对于当前查询,它返回我:
NodeId Leaf 2 0 6 1 <- I would like to stop recursivity here, but how? 7 0 27 1 28 1 8 1 9 1 10 1 93 0 11 1 12 1 13 0 25 1 24 1 14 1 4 0 15 1 16 1 17 0 23 1 22 1 5 0 18 0 21 1 20 1 19 1
我希望我能清楚地陈述我的情况,但总而言之,
我的问题是
:如果对同级中的同级进行排序,我如何进行递归查询以获取树的第一个分支?我能想到的解决此问题的唯一方法是,后处理给定的结果,并使用leaf
标志来停止遍历查询结果。但是,由于查询的节点离树的根部最近,查询花费的时间越长,结果集就越大,这是不理想的。
感谢您的帮助!
更新:我添加创建表并插入语句:
CREATE TABLE node (
Id INTEGER,
ParentId INTEGER REFERENCES node ( node_id ),
Sort INTEGER,
leaf BOOL,
PRIMARY KEY ( Id ) );
INSERT INTO node VALUES ( 1, NULL, 9, 0 );
INSERT INTO node VALUES ( 2, 1, 1, 0 );
INSERT INTO node VALUES ( 6, 2, 5, 1 );
INSERT INTO node VALUES ( 7, 2, 6, 0 );
INSERT INTO node VALUES ( 27, 7, 8, 1 );
INSERT INTO node VALUES ( 26, 7, 9, 1 );
INSERT INTO node VALUES ( 8, 2, 7, 1 );
INSERT INTO node VALUES ( 9, 2, 8, 1 );
INSERT INTO node VALUES ( 10, 2, 9, 1 );
INSERT INTO node VALUES ( 93, 1, 2, 0 );
INSERT INTO node VALUES ( 11, 93, 3, 1 );
INSERT INTO node VALUES ( 12, 93, 5, 1 );
INSERT INTO node VALUES ( 13, 93, 7, 0 );
INSERT INTO node VALUES ( 25, 13, 7, 1 );
INSERT INTO node VALUES ( 24, 13, 8, 1 );
INSERT INTO node VALUES ( 14, 93, 9, 1 );
INSERT INTO node VALUES ( 4, 1, 3, 0 );
INSERT INTO node VALUES ( 15, 4, 1, 1 );
INSERT INTO node VALUES ( 16, 4, 5, 1 );
INSERT INTO node VALUES ( 17, 4, 9, 0 );
INSERT INTO node VALUES ( 23, 17, 6, 1 );
INSERT INTO node VALUES ( 22, 17, 7, 1 );
INSERT INTO node VALUES ( 5, 1, 4, 0 );
INSERT INTO node VALUES ( 18, 5, 2, 0 );
INSERT INTO node VALUES ( 21, 18, 5, 1 );
INSERT INTO node VALUES ( 20, 18, 6, 1 );
INSERT INTO node VALUES ( 19, 5, 8, 1 );
我正在构建Xamarin.Forms应用程序。我在SQLite数据库中有一个表,该表以树形保存分层数据。我们称它为TreeNode:公共类TreeNode {[PrimaryKey] ...
诀窍是递归地仅选择具有最小排序值的兄弟行-这是当前父行的最左子级: