Я создаю приложение 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.
В качестве примера давайте рассмотрим следующее дерево, представляющее menu (извлечено из здесь ):
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, et c.
Я исследовал рекурсивные запросы за последние дни, и я могу пройти по вершине дерева. снизу (в ширину и в глубину), также я знаю, как получить всех предков данного узла. Есть множество примеров для этого.
Как я уже говорил в пункте 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 флаг, чтобы прекратить обходить результат запроса. Но это далеко не желательно, так как близко к root дерева запрашиваемого узла, чем дольше будет выполняться запрос и тем больше будет набор результатов.
Спасибо за вашу помощь!
ОБНОВЛЕНИЕ: я добавляю операторы создания таблицы и вставки:
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 );